## Computer Science 136 |

**Lecture 29: More AVL Trees, Graphs****Date: November 18, 2005**

- Darwin Lab continues.
- Computer Science Colloquium today, 2:35 p.m., TCL 206. The speaker is Hilary Hutchinson '97 from the University of Maryland. Title: "Children's Interface Design for Searching and Browsing".

- Finishing up AVL Trees - see complete examples below
- Graphs

* *

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*.

- Insertion into the left subtree of the left child of
*A*. - Insertion into the right subtree of the left child of
*A*. - Insertion into the left subtree of the right child of
*A*. - Insertion into the right subtree of the right child of
*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 *k _{1}* and

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 *k _{2}* to

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 *k _{1}* be 7,

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 *k _{1}* be 6,

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.