How to rebalance AVL tree after leaf deletion?
Here is how I think it should be done (after reading p. 652 of D.S.
Malik's "Data Structures using C++"). We traverse the path leading to the
deleted leaf starting from its parent. For every node P along this path we
do what is presented below. Suppoose the deletion has shorted the shorter
subtree of P and Q is the root of the taller subtree of P. Let bf() denote
balance_factor.
if |bf(P)|>1 and bf(Q) = 0, then rotate P
if |bf(P)|>1 and bf(Q) has the same sign as bf(P), then rotate P
if |bf(P)|>1 and bf(Q) has opposite sign to bf(P), then first rotate Q,
then rotate P (even if after Q's rotation bf(P) = 0 )
if |bf(P)|<2, then do nothing with P and proceed to P's parent
Is this correct?
No comments:
Post a Comment