Question 12.2.5: Write addition and deletion procedures that keep the tree ba......
Write addition and deletion procedures that keep the tree balanced.
The running time should not exceed C. (tree height). It is allowed to store additional information (needed for balancing) at the vertices of the tree.
For each vertex we keep the difference between the heights of its right and left subtrees:
diff [i] = (the height of the right subtree of i) -(the height of the left subtree of i).
We need four procedures that correspond to left/right, small/big rotations. Let us first make two remarks. (1) We want to keep the number of the tree root unchanged during the rotation. (Otherwise it would be necessary to update the pointer at the father vertex, which is inconvenient.) This can be done, because the numbers of tree vertices may be chosen independently of their content. (In our pictures, the number is drawn near the vertex while the content is drawn inside it.)
(2) After the transformation, we should update values in the diff array. To do this, it is enough to know the heights of trees P, Q, . . . up to a constant (only differences are important), so we may assume that one of the heights is equal to 0.
Here are the rotation procedures
| procedure SR (a:integer); {small right rotation at a} I var b: l..n; val_a,val b: T; h_P,h_Q,h_R: integer; begin b := right [a]; {b <> null} end ; procedure BR(a : integer) ;{big right rotation at a} b := right [a]; c := left [b]; {,c <> null} end; |
The (small and big) left rotations are similar.