www.delorie.com/gnu/docs/avl/libavl_158.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Now we're finally to the interesting part, the rebalancing step. We can tell whether rebalancing is necessary based on the balance factor of y, the same as in unthreaded AVL insertion:
if (y->tavl_balance == -2) { |
We will examine the case of insertion in the left subtree of y, the node at which we must rebalance. We take x as y's child on the side of the new node, then, as for unthreaded AVL insertion, we distinguish two cases based on the balance factor of x:
struct tavl_node *x = y->tavl_link[0]; if (x->tavl_balance == -1) { |
As for unthreaded insertion, we rotate right at y (see section 6.4.4 Step 4: Rebalance). Notice the resemblance of the following code to rotate_right() in the solution to Exercise 8.2-1.
w = x; if (x->tavl_tag[1] == TAVL_THREAD) |
When x has a + balance factor, we perform the transformation shown below, which consists of a left rotation at x followed by a right rotation at y. This is the same transformation used in unthreaded insertion:
We could simply apply the standard code from Exercise 8.2-1 in each rotation (see Exercise 1), but it is just as straightforward to do both of the rotations together, then clean up any threads. Subtrees a and d cannot cause thread-related trouble, because they are not disturbed during the transformation: a remains x's left child and d remains y's right child. The children of w, subtrees b and c, do require handling. If subtree b is a thread, then after the rotation and before fix-up x's right link points to itself, and, similarly, if c is a thread then y's left link points to itself. These links must be changed into threads to w instead, and w's links must be tagged as child pointers.
If both b and c are threads then the transformation looks like the diagram below, showing pre-rebalancing and post-rebalancing, post-fix-up views. The AVL balance rule implies that if b and c are threads then a and d are also:
The required code is heavily based on the corresponding code for unthreaded AVL rebalancing:
<@xref{\NODE\, , Rotate left at x.> then right at y in AVL tree; avl => tavl,156} if (w->tavl_tag[0] == TAVL_THREAD) |
Exercises:
1. Rewrite <@ref{\NODE\, , Rebalance for +.> balance factor in TAVL insertion in left subtree,307} in terms of the routines from Exercise 8.2-1. [answer]
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |