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

The most important problem is not the potential imbalance caused by
the remove algorithm. Rather, it is that, if the input sequence is sorted, the
worst-case tree occurs. When that happens, we are in deep trouble: We have
linear time per operation (for a series of N operations) rather than logarith-
mic cost per operation. This case is analogous to passing items to quicksort
but having an insertion sort executed instead. The resulting running time is
completely unacceptable. Moreover, it is not just sorted input that is prob-
lematic, but also any input that contains long sequences of nonrandomness.
One solution to this problem is to insist on an extra structural condition
called balance: No node is allowed to get too deep.

Any of several algorithms can be used to implement a balanced binary
search tree, which has an added structure property that guarantees logarithmic
depth in the worst case. Most of these algorithms are much more complicated
than those for the standard binary search trees, and all take longer on average
for insertion and deletion. They do, however, provide protection against the
embarrassingly simple cases that lead to poor performance for (unbalanced)
binary search trees. Also, because they are balanced, they tend to give faster
access time than those for the standard trees. Typically, their internal path
lengths are very close to the optimal N log N rather than 1.38 N log N, so
searching time is roughly 25 percent faster.

A balanced binary
search tree has an
added structure
property to guaran-
tee logarithmic
depth in the worst
case. Updates are
slower, but
accesses are faster.

avl trees

19.4

The first balanced binary search tree was the AVL tree (named after its dis-
coverers, Adelson-Velskii and Landis), which illustrates the ideas that are
thematic for a wide class of balanced binary search trees. It is a binary
search tree that has an additional balance condition. Any balance condi-
tion must be easy to maintain and ensures that the depth of the tree is
O (log N ). The simplest idea is to require that the left and right subtrees
have the same height. Recursion dictates that this idea apply to all nodes
in the tree because each node is itself a root of some subtree. This balance
condition ensures that the depth of the tree is logarithmic. However, it is
too restrictive because inserting new items while maintaining balance is
too difficult. Thus the definition of an AVL tree uses a notion of balance
that is somewhat weaker but still strong enough to guarantee logarithmic
depth.

The AVL tree was
the first balanced
binary search tree.
It has historical sig-
nificance and also
illustrates most of
the ideas that are
used in other
schemes.

definition: An AVL tree is a binary search tree with the additional balance prop-
erty that, for any node in the tree, the height of the left and right subtrees can
differ by at most 1. As usual, the height of an empty subtree is -1.