Binary search trees - Data Structures and Problem Solving Using Java - page 762

summary
Binary search trees support almost all of the useful operations in algorithm
design, and the logarithmic average cost is very small. Nonrecursive imple-
mentations of search trees are somewhat faster than recursive versions, but the
latter are sleeker, more elegant, and easier to understand and debug. The prob-
lem with search trees is that their performance depends heavily on the input's
being random. If it is not, running time increases significantly, even to the
point where search trees become expensive linked lists.
Ways of dealing with this problem all involve restructuring the tree to
ensure some sort of balance at each node. Restructuring is achieved
through tree rotations that preserve the binary search tree property. The
cost of a search is typically less than for an unbalanced binary search tree
because the average node tends to be closer to the root. Insertion and dele-
tion costs, however, are usually higher. The balanced variations differ in the
amount of coding effort involved in implementing operations that change
the tree.
The classic scheme is the AVL tree in which, for every node, the heights
of its left and right subtrees can differ by at most 1. The practical problem
with AVL trees is that they involve large numbers of different cases, making
the overhead of each insertion and deletion relatively high. We examined two
alternatives in the chapter. The first was the top-down red-black tree. Its pri-
mary advantage is that rebalancing can be implemented in a single pass down
the tree, rather than the traditional pass down and back up. This technique
leads to simpler code and faster performance than the AVL tree allows. The
second is the AA-tree, which is similar to the bottom-up red-black tree. Its
primary advantage is a relatively simple recursive implementation of both
insertion and deletion. Both structures use sentinel nodes to eliminate annoy-
ing special cases.
You should use an unbalanced binary search tree only if you are sure that
the data are reasonably random or that the amount of data is relatively small.
Use the red-black tree if you are concerned about speed (and are not too con-
cerned about deletion). Use the AA-tree if you want an easy implementation
that has more than acceptable performance. Use the B-tree when the amount
of data is too large to store in main memory.
In Chapter 22 we examine another alternative: the splay tree. It is an inter-
esting alternative to the balanced search tree, is simple to code, and is compet-
itive in practice. In Chapter 20 we examine the hash table, a completely
different method used to implement searching operations.