[next] [prev] [prev-tail] [tail] [up]

5.5.3 Rebalance implementation

It is best to make rebalance a subroutine by itself. This is because it may be triggered by node insertion and deletion.

When rebalance is called, it means the subtree pointed to by the parameter has two subtrees that are out of balance. However, it is up to the subroutine to figure out how it is out of balance, and how to reestablish the balance. There are only four cases to check, and each one has its solution.

Listing 1 is the template of a simple restructure (also called a rotation). This one is a clockwise rotation, which transforms ((TLL,nL,TLR),n,TR) to (TLL,nL,(TLR,n,TR)). The opposite rotation is symmetric, but with right and left reversed.

Oh, yes, the “?” symbols are there so that we can have a meaningful homework assignment derived from this module.


Listing 1:clockwise
 
1{ 
2  struct Tree *tmpTree = AVLTree_new(); 
3 
4  AVLTree_makealias(tmpTree, pTree); // *pTree is a, *tmpTree is a 
5  AVLTree_makealias(?,AVLTree_getlefttree(?)); 
6    // (x,n) becomes (x,nL), *pTree is b 
7  AVLTree_makealias(AVLTree_getlefttree(?),AVTTree_getrighttree(?)); 
8    // (nL, TLR) is duplicated to (n, TLR) 
9  AVLTree_makealias(AVLTree_getrighttree(?), ?); 
10    // (nL, TLR) becomes (nL,n) 
11  AVLTree_makeempty(tmpTree); 
12  AVLTree_delete(tmpTree); 
13}

[next] [prev] [prev-tail] [front] [up]