In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
from the keys to be sorted, and then traverses the tree (in-order
Tree traversal
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...
) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.
Efficiency
Adding one item to a binary search tree is on average an O(log(n)) process, so adding n items is an O(n log(n)) process, making Tree Sort a so-called, 'fast sort'. But adding an item to an unbalanced binary tree needs O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n) time in the worst-case, when the tree resembles a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
(degenerate tree), causing a worst case of O(n2) for this sorting algorithm.
The worst case scenario then is triggered by handing a Tree Sort algorithm an already sorted set. This would make the time needed to insert all elements into the binary tree O(n2). The dominant process in the Tree Sort algorithm is the "insertion" into the binary tree, assuming that the time needed for retrieval is O(n).
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
. Using such a tree, the algorithm has an O(n log(n)) worst-case performance, thus being degree-optimal.
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
) would look something like this:
data Tree a = Leaf | Node (Tree a) a (Tree a)
insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y t') | x <= y = Node (insert x t) y t'
insert x (Node t y t') | x > y = Node t y (insert x t')
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x t') = flatten t ++ [x] ++ flatten t'
treesort :: Ord a => [a] -> [a]
treesort = flatten . foldr insert Leaf
Mind that in the above example, both the insertion algorithm and the retrieval algorithm have O(n2) worst case scenarios.
