DinS Written on 2017/5/7
This is the second part of AVL Tree. See first part here.
5. Insert
Inserting a new node in AVL may cause the tree to be unbalanced, because this may change the height of subtrees. See an example here.
After inserting the node 12, the node 7, 13 and 5 all become unbalanced.
Concretely, balFact(7) = 0 – 2 = -2. balFact(13) = 3 – 1 = 2. balFact(5) = 2 – 4 = -2.
To fix the problem, we have to do some extra work after insertion. The key is rotations.
The insertion in AVL follows these steps:
(1) Apply the same insertion method in B.S.T.
(2) Check whether the AVL becomes unbalanced. If not, we’re done.
(3) If the tree becomes unbalanced, go along the new node’s parent to find the unbalanced node first encountered. We call it g. From g, find the taller child of g. We call it p. From p find the taller child of p. We call it v.
(4) Depending on the concrete position of g, p and v. We apply different method to rotate them.
Case I: if g, p, v are in a straight line, we apply left rotation or right rotation to g.
Case II: if g, p, v are in a zigzag position, we first apply left rotation to p then right rotation to g, or first apply right rotation to p then left rotation to g.
*口诀：三代同向用单旋，三代之字用双旋
First let’s see an example of case I.
After inserting node 12, node 7, 13 and 5 become unbalanced. We go along node 12’s parent to find the unbalanced node first encountered, which is node 7. From node 7 we locate node 10 as p, and node 12 as v.
Now that g, p, v are in a straight line (from left-up to right-down), we apply left rotation to g. If they were from right-up to left-down, we apply right rotation once.
The tree then becomes this.
Rotation won’t harm Search Tree Property. It reduces the height of subtrees too. Now this tree becomes balanced again.
Now let’s see an example of case II.
After inserting node 8, node 7, 13 and 5 become unbalanced. Thus we locate node 7 as g, node 10 as p and node 8 as v.
Since node 7, 10 and 8 are in a zigzag position, we first apply right rotation to p.
And the tree becomes like this. Now we apply left rotation to g.
Finally we get this.
The tree becomes balanced again. You may have noticed that after first rotation g, v, p were in a straight line again. This move made case II become case I. The second rotation is just a follow-up move in case I.
You may wonder why rotations help fix the unbalance problem. In general, if the tree becomes unbalanced after insertion, it must be the case that one subtree grows higher by 1. Using rotations we can reduce the subtree height by 1. Since before insertion the tree is an AVL and all nodes are balanced, this +1 and -1 make the tree to previous state again.
What’s the efficiency? Rotations take only O(1) time. To finding the unbalanced node first encountered we may need to travel from bottom to top. This takes O(height) = O(logn). In conclusion insertion in AVL takes O(logn).
6. Delete
Deletion is much harder than insertion in B.S.T. It is the same with AVL. After deletion AVL may become unbalanced. See this example.
After deleting node 47, node 13 becomes unbalanced. We need to do something to fix it. As is in insertion, rotation plays a key role.
The deletion in AVL follows these steps:
(1) Apply the same deletion method in B.S.T.
(2) Check whether the AVL becomes unbalanced. If not, we’re done.
(3) If the tree becomes unbalanced, go along the deleted node’s parent to find the unbalanced node first encountered. We call it g. From g, find the taller child of g. We call it p. From p find the taller child of p. We call it v.
(4) Depending on the position of g, p, v, we apply rotation(s) to them similar to methods used in insertion.
(5) After rotation(s), local subtree must be balanced again. However, the whole tree may still be unbalanced. We need to go along parents to check whether they are unbalanced. If we have found one, we then apply the same method to the node. This phenomenon is called unbalance spreading(失衡传播).
Let’s see a complicated example now. This example involves all the delicate parts of delete operations.
First we should check whether this is an AVL. I’ll leave the work to you. to help you, I’ve drawn the level lines on the picture. Using this you can easily confirm the height of trees. Second, I’d like to point out that for the root node 10, its balance factor is 4 – 5 = -1.
Now let’s delete node 1. Since it’s a leaf node, we simply delete it. After deletion, however, we have found that its parent node 2 becomes unbalanced. Its balance factor is 0 – 2 = -2.
We then locate the g, p, v nodes. Because they are in a zigzag position, we apply double rotations to fix it. First right rotate node 5. Second left rotate node 2.
After rotation we get this tree now.
Are we done? Not yet. After rotations, the local subtree has been balanced again, but note that the height of this subtree has decreased by 1. This means for the root node 10, its balance factor is now 3 – 5 = -2. Unbalance spreading has occurred! This, however, is not a big deal. We can apply the same method to fix this. First locate g, p, v nodes. Since they are in a straight line, we do left rotation to g. This changes the topological structure greatly.
After rotation we get this tree.
The unbalance has been fixed, and this is again an AVL.
Why will unbalance spreading occur? In general, we know that for a subtree S of height h in AVL, its left subtree and right subtree may have the height of h-1 and h-2. Suppose we delete a node in the h-2 branch. After rotation the height may decrease by 1. This causes the subtree to be of height h-3. Now subtree S becomes unbalanced. We apply the same method, and this may cause the subtree S to be of height h-1. Since S is shortened, the balance may continue to go upward till root.
Finally for the efficiency of deletion. To do deletion in B.S.T. we need O(height), which is O(logn) in AVL. Rotation takes only O(1). Unbalance spreading may cause us to do as many as O(logn) rotations. All in all, deletion in AVL takes O(logn). But note that to delete takes more work than insert, though they all take O(logn) time.
7. Conclusion
AVL is a powerful data structure. Search, insert and delete operations only takes O(logn). The downside is that delete operation may need O(logn) rotations, and change the topological structure dramatically. The good news is, as D. E. Knuth has showed, although delete operation needs O(logn) rotations in the worst case, on average it needs only 0.21 rotations.