|
|
Computer Science 136 |
Lecture 29: More AVL Trees, Graphs
Date: November 18, 2005
Since AVL trees are not covered in our text, I am providing more complete lecture notes about AVL trees:
Adelson-Velskii and Landis, 1962.
Balance condition: the heights of the left and right subtrees of any node can differ by at most 1.
To see that this is less strict than perfect balance, let's consider two trees:
5
/ \
2 8
/ \ /
1 4 7
/
3
This one satisfies the AVL condition (check the heights at each node).
But...
7
/ \
2 8
/ \
1 4
/ \
3 5
This one does not satisfy the AVL condition - the root node violates it!
So the goal is to maintain the AVL balance condition each time there is an insertion (we will ignore deletions, but similar techniques apply).
When inserting into the tree, a ndoe in the tree can become a violator of the AVL condition. Four cases can arise which characterize how the condition came to be violated. Call the violating node A.
In reality, however, there are only two really differnece cases, since cases 1 and 4 and cases 2 and 3 are mirror images of each other and similar methods apply.
First, we consider a violation of case 1.
We start with a tree that satisfies AVL:
We want to perform a single rotation to obtain an equivalent tree, but which satisfies AVL.
Essentially, we want to switch the roles of k1 and k2, resulting in this tree:
We can think of this like you have a handle for the subtree at the root and gravity determines the tree.
If we switch the handle from k2 to k1 and let things fall where they want (in fact, must), we have rebalanced.
Consider insertion of 3,2,1,4,5,6,7 into an originally empty tree.
Insert 3:
3
Insert 2:
3
/
2
Insert 1:
3 2
/ / \
2 ---> 1 3
/
1
Here, we had to do a rotation. We essentially replaced the root of the violating subtree with the root of the taller of its children.
Now, we insert 4:
2
/ \
1 3
\
4
Then insert 5:
2
/ \
1 3 <-- AVL violated here (case 4)
\
4
\
5
and we have to rotate at 3:
2
/ \
1 4
/ \
3 5
Now insert 6:
2 <-- AVL violated here (case 4)
/ \
1 4
/ \
3 5
\
6
Here, our rotation moves 4 to the root and everything else falls into place:
4
/ \
2 5
/ \ \
1 3 6
Finally, we insert 7:
4
/ \
2 5 <-- AVL violated here (case 4 again)
/ \ \
1 3 6
\
7
4
/ \
2 6
/ \ / \
1 3 5 7
Perfect balance, in this case (not guaranteed in general).
This example demonstrates the application of cases 1 and 4, but not cases 2 and 3.
Here's case 2:
We start again with the good tree:
We know subtree Y is not empty, so let's draw our tree as follows:
We are guaranteed to correct it by moving D down a level and both B and C up a level:
In reality, only one of B and C is at level n - the other only descends to level n-1.
Case 3 is the mirror image of this.
To see examples of this, let's pick up the previous example, which had constructed a perfectly-balanced tree of the values 1-7.
4
/ \
2 6
/ \ / \
1 3 5 7
At this point, we insert a 16, then a 15 to get:
4
/ \
2 6
/ \ / \
1 3 5 7
\
16
/
15
Node 7 violates AVL and this happened because of an insert into the left subtree of its right child. Case 3.
So we let k1 be 7, k2 be 15, and k3 be 16 and rearrange them to have k2 at the root of the subtree, with children k1 and k3. Here, the subtrees A, B, C, and D are all empty.
We get:
4
/ \
2 6
/ \ / \
1 3 5 15
/ \
7 16
Now insert 14.
4
/ \
2 6
/ \ / \
1 3 5 15
/ \
7 16
\
14
This violates AVL at node 6 (one child of height 0, one of height 2).
This is again an instance of case 3: insertion into the left subtree of the right child of the violating node.
So we let k1 be 6, k2 be 7, and k3 be 15 and rearrange them again. This time, subtrees A is the 5, B is empty, C is the 14, and D is the 16.
The double rotation requires that 7 become the root of that subtree, the 6 and the 15 its children, and the other subtrees fall into place:
4
/ \
2 7
/ \ / \
1 3 6 15
/ / \
5 14 16
Insert 13:
4
/ \
2 7
/ \ / \
1 3 6 15
/ / \
5 14 16
/
13
What do we have here? Looking up from the insert location, the first element that violates the balance condition is the root, which has a difference of two between its left and right child heights.
Since this is an insert into the right subtree of the right child, case 4. This requires just a single rotation, but one done all the way at the root. We get:
7
/ \
4 15
/ \ / \
2 6 14 16
/ \ / /
1 3 5 13
Now adding 12:
7
/ \
4 15
/ \ / \
2 6 14 16
/ \ / /
1 3 5 13
/
12
The violation this time is at 14, which is a simple single rotation (case 1):
7
/ \
4 15
/ \ / \
2 6 13 16
/ \ / / \
1 3 5 12 14
Inserting 11:
7
/ \
4 15
/ \ / \
2 6 13 16
/ \ / / \
1 3 5 12 14
/
11
Here, we have a violation at 15, case 1, so another single rotation there, promoting 13:
7
/ \
4 13
/ \ / \
2 6 12 15
/ \ / / / \
1 3 5 11 14 16
(Almost done)
Insert 10:
7
/ \
4 13
/ \ / \
2 6 12 15
/ \ / / / \
1 3 5 11 14 16
/
10
The violator here is 12, case 1:
7
/ \
4 13
/ \ / \
2 6 11 15
/ \ / / \ / \
1 3 5 10 12 14 16
Then we finally add 8 (no rotations needed) then 9:
7
/ \
4 13
/ \ / \
2 6 11 15
/ \ / / \ / \
1 3 5 10 12 14 16
/
8
\
9
Finally we see case 2 and do a double rotation with 8, 9, and 10 to get our final tree:
7
/ \
4 13
/ \ / \
2 6 11 15
/ \ / / \ / \
1 3 5 9 12 14 16
/ \
8 10
This tree is not strictuly balanced - we have a hole under 6's right child, but it does satify AVL.
Think about how we might implement an AVL tree.