www.delorie.com/gnu/docs/avl/libavl_164.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Rebalancing after deletion in a TAVL tree divides into three cases. The first of these is analogous to case 1 in unthreaded AVL deletion, the other two to case 2 (see section 8.6 Insertion). The cases are distinguished, as usual, based on the balance factor of right child x of the node y at which rebalancing occurs:
struct tavl_node *x = y->tavl_link[1]; assert (x != NULL); if (x->tavl_balance == -1) |
This case is just like case 2 in TAVL insertion. In fact, we can even reuse the code:
struct tavl_node *w; <@xref{\NODE\, , Rebalance for -.> balance factor in TAVL insertion in right subtree,310} q->tavl_link[dir] = w; |
If x has a 0 balance factor, then we perform a left rotation at y. The transformation looks like this, with subtree heights listed under their labels:
Subtree b is taller than subtree a, so even if h takes its minimum value of 1, then subtree b has height h == 1 and, therefore, it must contain at least one node and there is no need to do any checking for threads. The code is simple:
y->tavl_link[1] = x->tavl_link[0]; x->tavl_link[0] = y; x->tavl_balance = -1; y->tavl_balance = +1; |
If x has a + balance factor, we perform a left rotation at y, same as for case 2, and the transformation looks like this:
One difference from case 2 is in the resulting balance factors. The other is that if h == 1, then subtrees a and b have height h - 1 == 0, so a and b may actually be threads. In that case, the transformation must be done this way:
This code handles both possibilities:
if (x->tavl_tag[0] == TAVL_CHILD) y->tavl_link[1] = x->tavl_link[0]; else |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |