Page 149 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 3
Daisy
2 2
Eunice
Binky
1 1 0
Baby Calista Dontonio 1
Daisy Luther
0 0 0
Ahmed Boo 0
Fred Waluigi

Deletion

When you delete a node, there are three things that can happen to the parent:
1. Its height is decremented by one. An example of this is if Boo is deleted from the above
tree – Baby Daisy’s height is decremented by one.

2. Its height doesn’t change and it stays balanced. An example of this is if Fred is deleted --
Luther’s height is unchanged and it is balanced.
3. Its height doesn’t change, but it becomes imbalanced. An example of this is if Dontonio is
deleted – Eunice’s height is unchanged, but she is imbalanced.
You handle these three cases in different ways:
1. The parent’s height is decremented by one. When this happens, you check the parent’s
parent: you keep doing this until you return or you reach the root of the tree.

2. The parent’s height doesn’t change and it stays balanced. When this happens you may
return – deletion is over.
3. The parent’s height doesn’t change, but it becomes imbalanced. When this happens, you
have to rebalance the subtree rooted at the parent. After rebalancing, the subtree’s height
may be one smaller than it was originally. If so, you must continue checking the parent’s
parent.
To rebalance, you need to identify whether you are in a zig-zig situation or a zig-zag situation
and rebalance accordingly. How do you do this? Look at the following picture:

h
B

h-3 h-1
D
A

h-3 or h-4

C E

h-2 or h-3 h-2 or h-3
Imbalanced Identification Picture

144 LOVELY PROFESSIONAL UNIVERSITY