Tree sort

Tree sort

Class	Sorting algorithm
Data structure	Array
Worst case performance	O(n2) (unbalanced) O(n log n) (balanced)
Best case performance	O(n)
Average case performance	O(n log n)

A tree sort is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree (in-order) 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(n) time in the worst-case, when the tree resembles a linked list (degenerate tree), causing a worst case of O(n²) 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(n²). 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).

The worst-case behaviour can be improved upon by using a self-balancing binary search tree. Using such a tree, the algorithm has an O(n log(n)) worst-case performance, thus being degree-optimal.

Example

The following tree sort algorithm in pseudocode accepts an array of comparable items and prints them to the screen in ascending order:

STRUCTURE BinaryTree
    BinaryTree:LeftSubTree
    Object:Node
    BinaryTree:RightSubTree
END STRUCTURE
 
PROCEDURE Insert(BinaryTree:searchTree, Object:item)
    IF searchTree IS NULL THEN
        SET searchTree.Node TO item
    ELSE
        IF item IS LESS THAN searchTree.Node THEN
            Insert(searchTree.LeftSubTree, item)
        ELSE
            Insert(searchTree.RightSubTree, item)
        END IF
    END IF
END PROCEDURE
 
PROCEDURE InOrder(BinaryTree:searchTree)
    IF searchTree IS NULL THEN
        EXIT PROCEDURE
    ELSE
        InOrder(searchTree.LeftSubTree)
        PRINT searchTree.Node
        InOrder(searchTree.RightSubTree)
    END IF
END PROCEDURE
 
PROCEDURE TreeSort(Array:items)
    BinaryTree:searchTree
 
    FOR EACH individualItem IN items
        Insert(searchTree, individualItem)
    END FOR
 
    InOrder(searchTree)
END PROCEDURE

In a simple functional programming form, the algorithm (in Haskell) 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 s) | x <= y = Node (insert x t) y s
insert x (Node t y s) | x > y = Node t y (insert x s)
 
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x s) = flatten t ++ [x] ++ flatten s
 
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(n²) worst case scenarios.

External links

• Binary Tree Java Applet and Explanation
• Tree Sort of a Linked List
• Tree Sort in C++