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


GNU libavl 2.0.1

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

15.4.2 Step 3: Update Balance Factors

Until now, in step 3 of insertion into AVL trees we've always updated balance factors from the top down, starting at y and working our way down to n (see, e.g., &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 3: Update balance factors after AVL insertion,150}). This approach was somewhat unnatural, but it worked. The original reason we did it this way was that it was either impossible, as for AVL and RTAVL trees, or slow, as for TAVL trees, to efficiently move upward in a tree. That's not a consideration anymore, so we can do it from the bottom up and in the process eliminate the cache used before.

At each step, we need to know the node to update and, for that node, on which side of its parent it is a child. In the code below, q is the node and dir is the side.

 
for (p = n; p != y; p = q) 
{ q = p-&#62;pavl_parent; dir = q-&#62;pavl_link[0] != p; if (dir == 0) q-&#62;pavl_balance--; else
q-&#62;pavl_balance++; }
This code is included in @refalso{523

Exercises:

1. Does this step 3 update the same set of balance factors as would a literal adaptation of &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 3: Update balance factors after AVL insertion,150}? [answer]

2. Would it be acceptable to substitute q-&#62;pavl_link[1] == p for q-&#62;pavl_link[0] != p in the code segment above? [answer]


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