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

GNU libavl 2.0.1

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

Chapter 14

Section 14.2

static void 
rotate_right (struct pbst_node **yp)
{ struct pbst_node *y = *yp; struct pbst_node *x = y-&#62;pbst_link[0]; y-&#62;pbst_link[0] = x-&#62;pbst_link[1]; x-&#62;pbst_link[1] = y; *yp = x; x-&#62;pbst_parent = y-&#62;pbst_parent; y-&#62;pbst_parent = x; if (y-&#62;pbst_link[0] != NULL) y-&#62;pbst_link[0]-&#62;pbst_parent = y; }

static void 
rotate_left (struct pbst_node **xp)
{ struct pbst_node *x = *xp; struct pbst_node *y = x-&#62;pbst_link[1]; x-&#62;pbst_link[1] = y-&#62;pbst_link[0]; y-&#62;pbst_link[0] = x; *xp = y; y-&#62;pbst_parent = x-&#62;pbst_parent; x-&#62;pbst_parent = y; if (x-&#62;pbst_link[1] != NULL) x-&#62;pbst_link[1]-&#62;pbst_parent = x; }

Section 14.4.2

1. Yes. Both code segments update the nodes along the direct path from y down to n, including node y but not node n. The plain AVL code excluded node n by updating nodes as it moved down to them and making arrival at node n the loop's termination condition. The PAVL code excludes node n by starting at it but updating the parent of each visited node instead of the node itself.

There still could be a problem at the edge case where no nodes' balance factors were to be updated, but there is no such case. There is always at least one balance factor to update, because every inserted node has a parent whose balance factor is affected by its insertion. The one exception would be the first node inserted into an empty tree, but that was already handled as a special case.

2. Sure. There is no parallel to Exercise 5.4.4-4 because q is never the pseudo-root.

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