Chapter 13

Section 13.4

1. No. It would work, except for the important special case where q is the pseudo-root but p->pbst_parent is NULL.

Section 13.7

1.

681. <PBST balance function, with integrated parent updates 681> =
<BST to vine function; bst => pbst 90>
<Vine to balanced PBST function, with parent updates 682>

void 
pbst_balance (struct pbst_table *tree) 
{
  assert (tree != NULL);

  tree_to_vine (tree);
  vine_to_tree (tree);
}

682. <Vine to balanced PBST function, with parent updates 682> =
<PBST compression function 684>

static void 
vine_to_tree (struct pbst_table *tree) 
{
  unsigned long vine;      /* Number of nodes in main vine. */
  unsigned long leaves;    /* Nodes in incomplete bottom level, if any. */
  int height;              /* Height of produced balanced tree. */
  struct pbst_node *p, *q; /* Current visited node and its parent. */

  <Calculate leaves; bst => pbst 92>
  <Reduce vine general case to special case; bst => pbst 93>
  <Make special case vine into balanced tree and count height; bst => pbst 94>
  <Set parents of main vine 683>
}

This code is included in 681.

683. <Set parents of main vine 683> =
for (q = NULL, p = tree->pbst_root; p != NULL; q = p, p = p->pbst_link[0])
  p->pbst_parent = q;

This code is included in 682.

684. <PBST compression function 684> =
static void 
compress (struct pbst_node *root, unsigned long count) 
{
  assert (root != NULL);

  while (count--) 
    {
      struct pbst_node *red = root->pbst_link[0];
      struct pbst_node *black = red->pbst_link[0];

      root->pbst_link[0] = black;
      red->pbst_link[0] = black->pbst_link[1];
      black->pbst_link[1] = red;
      red->pbst_parent = black;
      if (red->pbst_link[0] != NULL)
        red->pbst_link[0]->pbst_parent = red;
      root = black;
    }
}

This code is included in 682.