As described earlier, binary search trees perform well only
if the tree remains balanced. Unfortunately, keeping a binary search
tree balanced is a more difficult problem than it may at first appear.
Nevertheless, there are a few clever approaches one can take. One of
the best approaches is to implement the tree as an *AVL
tree*.

An AVL (Adel'son-Vel'skii and Landis) tree is a special type of
binary tree that stores an extra piece of information with each node:
its *balance factor* . The balance factor of a node is the height of the
subtree rooted at its left child minus the height of the subtree
rooted at its right child (see Figure
9.9). As nodes are inserted, an AVL tree adjusts itself so that
all balance factors stay +1, -1, or 0. A subtree whose root node has a
balance factor of +1 is said to be *left-heavy*. A
subtree whose root node has a balance factor of -1 is said to be
*right-heavy*. A subtree whose root node has a
balance factor of is considered balanced. By keeping its subtrees
nearly balanced, an AVL tree stays *approximately*
balanced overall.

Figure 9.9. An AVL tree, including balance factors

The basic means of searching and inserting nodes in an AVL tree is the same as described earlier. However, when we insert a node into an AVL tree, we have some additional work to do after the node descends to its appropriate position. First, ...

Start Free Trial

No credit card required