Page 145 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes This is a tree which can now be balanced using a single right rotation. We can now perform our
right rotation rooted at C. The result:
b
/ \
a c
Balance at last.

AVL Operation

Insertion into AVL Trees

To implement AVL trees, you need to maintain the height of each node. You insert into an AVL
tree by performing a standard binary tree insertion. When you’re done, you check each node
on the path from the new node to the root. If that node’s height hasn’t changed because of the
insertion, then you are done. If the node’s height has changed, but it does not violate the balance
property, then you continue checking the next node in the path. If the node’s height has changed
and it now violates the balance property, then you need to perform one or two rotations to fi x the
problem, and then you are done.
Let’s try some examples. Suppose I have the following AVL tree -- I now annotate the nodes with
their heights:
3
Eunice
2 1
Fred
Binky
0 1 0
Baby Daisy
Daisy Luther
0
Calista

If I insert Ahmad, take a look at the resulting tree:
3
Eunice
2 1
Fred
Binky
1 1 0
Baby Daisy Luther
Daisy
0
0
Ahmed Calista

The new node Ahmad has a height of zero, and when I travel the path up to the root, I change
Baby Daisy’s height to one. However, her node is not imbalanced, since the height of her subtrees
are 0 and -1. Moving on, Binky’s height is unchanged, so we can stop – the resulting tree is indeed
an AVL tree.

140 LOVELY PROFESSIONAL UNIVERSITY