www.delorie.com/gnu/docs/avl/libavl_163.html   search  
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.5.3 Step 3: Update Balance Factors

Rebalancing begins from node q, from whose side dir a node was deleted. Node q at the beginning of the iteration becomes node y, the root of the balance factor update and rebalancing, and dir at the beginning of the iteration is used to separate the left-side and right-side deletion cases.

The loop also updates the values of q and dir for rebalancing and for use in the next iteration of the loop, if any. These new values can only be assigned after the old ones are no longer needed, but must be assigned before any rebalancing so that the parent link to y can be changed. For q this is after y receives q's old value and before rebalancing. For dir, it is after the branch point that separates the left-side and right-side deletion cases, so the dir assignment is duplicated in each branch. The code used to update q is discussed later.

while (q != (struct tavl_node *) &tree-&#62;tavl_root) 
{ struct tavl_node *y = q; q = find_parent (tree, y); if (dir == 0)
{ dir = q-&#62;tavl_link[0] != y; y-&#62;tavl_balance++; if (y-&#62;tavl_balance == +1) break; else if (y-&#62;tavl_balance == +2) {
&#60;@xref{\NODE\, , Step 4: Rebalance after TAVL deletion.&#62;,319}
} } else
&#60;@xref{\NODE\, , Steps 3 and 4: Symmetric case in TAVL deletion.&#62;,323}
} } tree-&#62;tavl_count--; return (void *) item;
This code is included in @refalso{311

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003