Chapter 14

Section 14.2

1.

/* Rotates right at *yp. */
static void 
rotate_right (struct pbst_node **yp) 
{
  struct pbst_node *y = *yp;
  struct pbst_node *x = y->pbst_link[0];
  y->pbst_link[0] = x->pbst_link[1];
  x->pbst_link[1] = y;
  *yp = x;
  x->pbst_parent = y->pbst_parent;
  y->pbst_parent = x;
  if (y->pbst_link[0] != NULL)
    y->pbst_link[0]->pbst_parent = y;
}

/* Rotates left at *xp. */
static void 
rotate_left (struct pbst_node **xp) 
{
  struct pbst_node *x = *xp;
  struct pbst_node *y = x->pbst_link[1];
  x->pbst_link[1] = y->pbst_link[0];
  y->pbst_link[0] = x;
  *xp = y;
  y->pbst_parent = x->pbst_parent;
  x->pbst_parent = y;
  if (x->pbst_link[1] != NULL)
    x->pbst_link[1]->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.

Chapter 13

Appendix D Answers to All the Exercises

Appendix E Catalogue of Algorithms