Page 147 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Node D is the new root of the subtree. Before the insertion, node B’s height was h-1, so the height
of the subtree has not changed because of the rotation. Thus, insertion is over, and you are left
with a valid AVL tree.
If the path from the imbalanced node to the newly added node starts with two left children, then
you have another Zig-Zig case (the mirror image). You treat it in the same way: rotate about the
imbalanced node’s left child.

Before going on, take a look at our example above where Fred was imbalanced. That is a Zig-Zig

case, so we can fix it by rotating about Luther:
3 Eunice 3
Eunice
2 2 Rotate about Luther 2 Luther 1
Binky Fred Binky
1 1 1 1 1 0
Baby Daisy Luther Baby Daisy Fred Waluigi
Daisy Daisy
0 0 0 0 0
Ahmed Calista Waluigi Ahmed Calista

The other rebalancing case is the Zig-Zag case, pictured below:
h
B

h-1
h-3 F Either D is the
newly added
A node, or it is a
h-2 h-3 node in C or E.
D
G

C E
h-3 or h-4 h-3 or h-4

To fix this, you perform two rotations. You rotate about node D, and then you rotate about node
D again. This is called a double rotation about node D. Here are the two rotations:
h
B

h-1
h-3 D

A
h-2
F
C

h-3 or h-4 h-3

E G
h-3 or h-4
First rotation about D.

142 LOVELY PROFESSIONAL UNIVERSITY