READING:
"Data Structures and Algorithm Analysis in C", M A Weiss – Chapter 4, section 4
Answers:Periodically test the tree to see how imbalanced it has become (e.g. using the FindMaxDepth function from Lecture 8). If it goes beyond a predefined point we can rebuild the tree so that it becomes balanced again. In this way we can keep using our simple (and therefore fast) insertion and deletion algorithms. Use better insertion and deletion algorithms so that the tree remains balanced after each insertion and deletion (i.e AVL). |
|
|
|
AVL tree |
non-AVL tree |
fully balanced tree |
The definition of an AVL tree is important because fairly simple algorithms exist to insert and delete from an AVL tree without destroying the AVL property. |
Single Right Rotation
(Weiss Figure 4.31)
Note that the original right sub-tree of k1(Y) becomes the new left sub-tree of k2: this is the only way that the keys will still remain in the correct order. This fixes case 1 above. Consider the alternative case where the largest sub-tree is on the far right: |
Single Left Rotation
(Weiss Figure 4.33)
This fixes case 4. This is called single left rotation because the root of the imbalanced tree is rotated left becoming the root of the left sub-tree. To make this clearer consider the following example: |
(Weiss Figure 4.34)
Instead we use a procedure called double rotation where we move the root of the root of the larger sub-tree to be the root of the original imbalanced tree: |
First we rotate k2 to the left: |
Now we have the longer sub-tree on the far left so we are back in a situation we have already considered and a right rotation will restore the tree’s balance: |
(Weiss Figure 4.35)
The previous manipulation was a left rotation around the root of the left sub-tree, then a right rotation around the root of the original sub-tree. Hence it is called a left right double rotation. Note it still uses the basic rotation actions used in the simpler examples. The final case is where the inner sub-tree on the right hand side is the larger tree. This is the mirror of the previous example and is fixed with a right left double rotation: |
(Weiss Figure 4.36)
To make this clearer, consider the following tree: |
|
Here we insert 15 which makes the tree imbalanced at 9: 9’s left sub-tree has height 0, the right sub-tree has height 2. Because the larger subtree is to the left of 16 (ie it is between the values of 9 and 16), we need to do a right left double rotation. |
First we rotate to the right with 16 as the root |
Then rotate left with 9 as the root |
|
|
The algorithm for AVL insertion follows the same structure as our earlier InsertNode algorithm except we have to keep track of the height of each node and test for each of the 4 situations described above: |
InsertAVLNode(NewValue, Root) { if(!Root){ Root = allocate memory for node; Root->Value = NewValue; Root->Height = 0; Root->Left = Root->Right = NULL; } else if(NewValue < Root->Value){ Root->Left=InsertAVLNode(NewValue,Root->Left); if(Root->Left->Height-Root->Right->Height == 2) if(NewValue < Root->Left->Value) Root = SingleRightRotation(Root); else Root = DoubleLeftRightRotation(Root); } else if(NewValue > Root->Value){ Root->Right=InsertAVLNode(NewValue,Root->Right); if(Root->Right->Height-Root->Left->Height == 2) if(NewValue < Root->Right->Value) Root = SingleLeftRotation(Root); else Root = DoubleRightLeftRotation(Root); if(Root->Left->Height >= Root->Right->Height) Root->Height = Root->Left->Height + 1; else Root->Height = Root->Right->Height + 1; return Root; } |
The action of rotation is fairly simple: SingleRightRotation(Root) { NewRoot = Root->Left; Root->Left = NewRoot->Right; NewRoot->Right = Root; if(Root->Left->Height >= Root->Right->Height) Root->Height = Root->Left->Height + 1; else Root->Height = Root->Right->Height + 1; if(NewRoot->Left->Height >= NewRoot->Right->Height) NewRoot->Height = NewRoot->Left->Height +1; else NewRoot->Height = NewRoot->Right->Height+1; return NewRoot; } |
A single left rotation is just a mirror of a right rotation. Given single left and right rotation functions, a double rotation becomes trivial: DoubleRightLeftRotation(Root) { Root->Right = SingleRightRotation(Root->Right); return SingleLeftRotation(Root); } Again the case for a double left right rotation is the mirror of the above function. |
Consider an example: |
|
Delete 5:
|
|
|
The above example leaves the tree balanced so no further action is required. However as with insertion, a deletion may cause a left and right sub-tree to become unbalanced. In this case we can use the same rotation techniques introduced for insertion to rebalance the tree. This again (of course) involves updating the height of each sub-tree that is changed by a deletion. |
ConclusionsThe AVL tree requires more coding work than a simple random binary tree, but provides better and better performance as n gets larger. Therefore in an application that requires a binary tree, where performance is important and n is large, the AVL tree would be the preferred data structure. |