Database Reference
In-Depth Information
Searching for a node in this BST would be reduced to searching a linear linked list!
Solving this problem is not trivial. It is generally referred to as balancing the tree. Several
algorithms have been proposed for balancing a BST.
A1.5 Height-Balanced Trees
A height-balanced k-tree (denoted (HB (k)) is a BST in which the maximum allowable
difference in height between any two sub-trees sharing a common root (not necessary a
parent) is k. Put another way, the maximum possible difference in height between leaves
of the tree is k.
An AVL tree (named after Adelson-Velskii and Landis, the Russian founders) is a
HB (1) tree, that is, the maximum possible difference in height between any two sub-trees
sharing a common root is 1. Put another way, leaves are either at level m or level m + 1.
Figure
A1-14
provides some illustrations. Heaps (discussed next) are also examples of
HB trees.
Figure A1-15.
Illustrating AVL and non-AVL Trees
