Balancing AVL Trees

cosc 2030 AVL Trees

Last Lecture In the last lecture we showed that, for an average binary search tree, the average depth of the nodes is about log N, where N is the number of nodes. This is quite amazing, indicating that the bad situations, which are linear, don t occur very often. However, for those who are still concerned about the very bad situations, we can try to balance the trees. This is the subject for today.

Balancing Trees What does it mean to balance trees? The basic idea is to make sure that the trees aren t right-heavy or left-heavy. When they are right-heavy or left-heavy, the trees need to be adjusted.

1 Example 2 3 Here is a right-heavy tree. How can we adjust it to be more balanced??? 4 5 6 7

Attempt #1 4 5 3 6 2 1 7 Attempt #1: Require that the left and right subtrees of the root node have the same height. X We can do better.

Attempt #2 4 2 6 1 3 5 7 Attempt #2: Require that every node have left and right subtrees of the same height. X Too restrictive.

Attempt #3 violated at node 4 4 4 2 2 6 6 1 3 5 1 3 0 0 Attempt #3: Require that, for every node, the height of the left and right subtrees can differ by most one. The example on the left satisfies attempt #3, while the one on the right does not. This rule is a nice compromise between too lax and too restrictive.

Repair Suppose the tree violates a balance condition. How and when can it be repaired? Repair is accomplished via tree rotations . Repair is done either during insertions, or after access of a node (because during access one notices the node is very deep and should be made more shallow).

AVL Trees AVL (Adelson-Velskii and Landis) trees are binary search trees that follow attempt #3. When a tree violates #3 a repair is done. The repair is done during insertions, as soon as #3 is violated. The repair is accomplished via single and double rotations.

Single Rotation k2 k1 k1 k2 h Z X X Y Y Z New item Suppose an item is added at the bottom of subtree X, thus causing an imbalance at k2. Then pull k1 up. Note that after the rotation, the height of the tree is the same as it was before the insertion.

Example 4 2 4 2 6 1 3 6 1 3 0 0 Imbalance at node 4 solved with single rotation.

Another Single Rotation k1 k2 k1 k2 h Z X X Y Z Y Suppose an item is added at the bottom of subtree X, thus causing an imbalance at k2. Then pull k1 up. Note that after the rotation, the height of the tree is the same as it was before the insertion.

Another Example 6 4 8 2 4 6 2 10 5 5 8 10 Imbalance at node 4 solved with single rotation.

Single Rotations After single rotations, the new height of the entire subtree is exactly the same as the height of the original subtree prior to the insertion of the new data item that caused X to grow. Thus no further updating of heights on the path to the root is needed, and consequently no further rotations are needed.

Double Rotation k2 k3 k1 k1 k3 h D k2 C B A A D B C or or Suppose an item is added below k2. This causes an imbalance at k3. Then pull k2 up. Note that after the rotation, the height of the tree is the same as it was before the insertion.

Another Double Rotation k2 k3 k3 k1 k1 h A k2 B C D A D B C or or Suppose an item is added below k2. This causes an imbalance at k3. Then pull k2 up. Note that after the rotation, the height of the tree is the same as it was before the insertion.

An Example 4 4 2 2 6 6 1 5 1 5 8 9 10 10 8 9 Imbalance at node 8 solved with double rotation.

Which Rotation Do I Use? Recognizing which rotation you have to use is the hardest part. Find the imbalanced node. Go down two nodes towards the newly inserted node. If the path is straight, use single rotation. If the path zig-zags, use double rotation.

Double Rotation= 2 Single Rotations k3 k1 D k2 A C B First do a single rotation of k2 and k1.

Double Rotation= 2 Single Rotations k3 k2 D k1 C A B But k3 still imbalanced, so do a single rotation of k2 and k3.

Double Rotation= 2 Single Rotations k2 k1 k3 C A B D Now we are done.

Double Rotations As with the single rotations, double rotations restore the height of the subtree to what it was before the insertion. This guarantees that all rebalancing and height updating is complete.

Using C++ k2 k1 k1 k2 h Z X New Item X Y Y Z New item void SingleRotateRight (AvlNode *&k2) const { AvlNode *k1 = k2->left; // get left child of k2, which be a new root. k2->left = k1->right; //Move y tree from k1 to k2's left. k1->right = k2; //make k2 the k1 right child. k2 = k1; //put k1 as the root of the tree. }

Using C++ k2 k3 k1 k1 k3 h D k2 A A B C D C B void DoubleRotate1 (AvlNode *&k3) const { SingleRotateLeft( k3->left ); //move k2 up to k1 position, left rotate. SingleRotateRight( k3 ); //now move k2 to the right, taking the root position }

Conclusions AVL trees maintain balance of binary search trees while they are being created via insertions of data. An alternative approach is to have trees that readjust themselves when data is accessed, making often accessed data items move to the top of the tree. Splay Trees Note, we will not be covering splay trees, but you should know they exist. Why would splay trees be useful?

QA &