www.delorie.com/gnu/docs/avl/libavl_105.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Now we have to write code to rebalance when it becomes necessary. We'll use rotations to do this, as before. Again, we'll distinguish the cases on the basis of x's balance factor, where x is y's right child:
struct avl_node *x = y->avl_link[1]; if (x->avl_balance == -1) { |
If x has a - balance factor, we handle rebalancing in a manner analogous to case 2 for insertion. In fact, we reuse the code. We rotate right at x, then left at y. w is the left child of x. The two rotations look like this:
struct avl_node *w; <@xref{\NODE\, , Rotate right at x.> then left at y in AVL tree,159} pa[k - 1]->avl_link[da[k - 1]] = w; |
When x's balance factor is +, the needed treatment is analogous to Case 1 for insertion. We simply rotate left at y and update the pointer to the subtree, then update balance factors. The deletion and rebalancing then look like this:
When x's balance factor is 0, we perform the same rotation, but the height of the overall subtree does not change, so we're done and can exit the loop with break. Here's what the deletion and rebalancing look like for this subcase:
y->avl_link[1] = x->avl_link[0]; x->avl_link[0] = y; pa[k - 1]->avl_link[da[k - 1]] = x; if (x->avl_balance == 0) |
Exercises:
1. In <@xref{\NODE\, , Step 4: Rebalance after AVL deletion.>,173}, we refer to fields in x, the right child of y, without checking that y has a non-null right child. Why can we assume that node x is non-null? [answer]
2. Describe the shape of a tree that might require rebalancing at every level above a particular node. Give an example. [answer]
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |