It is a binary tree whose nodescontain elements of a set of orderable items, one element per node, so that all elementsin the left subtree are smaller than the element in the subtree’s root, and allthe elements in the right subtree are greater than it. Note that this transformationfrom a set to a binary search tree is an example of the representation-change technique.What do we gain by such transformation compared to the straightforwardimplementation of a dictionary by, say, an array? We gain in the time efficiencyof searching, insertion, and deletion, which are all in bigtheta(log n), but only in the averagecase. In the worst case, these operations are in bigtheta(n) because the tree candegenerate into a severely unbalanced one with its height equal to n − 1.
Computer scientists have expended a lot of effort in trying to find a structure that preserves the good properties of the classical binary search tree—principally, the logarithmic efficiency of the dictionary operations and having the set’s elements sorted—but avoids its worst-case degeneracy. They have come up with two approaches.
AVL Trees
An AVL tree is a binary search tree in which the balance factor of every node, which is defined as the difference between the heights of the node’s left and right subtrees, is either 0 or +1 or −1. (The height of the empty tree is defined as−1.
If an insertion of a new node makes an AVL tree unbalanced, we transform the tree by a rotation. A rotation in an AVL tree is a local transformation of its subtree rooted at a node whose balance has become either +2 or −2. If there are several such nodes, we rotate the tree rooted at the unbalanced node that is the closest to the newly inserted leaf. There are only four types of rotations; in fact, two of them are mirror images of the other two.
The first rotation type is called the single right rotation, or R-rotation. (Imagine rotating the edge connecting the root and its left child in the binary tree in Figure 6.3a to the right.) Figure 6.4 presents the single R-rotation in its most general form. Note that this rotation is performed after a new key is inserted into the left subtree of the left child of a tree whose root had the balance of +1 before the insertion.
The symmetric single left rotation, or L-rotation, is the mirror image of the single R-rotation. It is performed after a new key is inserted into the right subtree of the right child of a tree whose root had the balance of −1 before the insertion.
- 1 more item...
