10.9 Balance

As for so many other operations, we can reuse most of the TBST balancing code to rebalance RTBSTs. Some of the helper functions can be completely recycled:

408. <RTBST balance function 408> =
<RTBST tree-to-vine function 409>
<RTBST vine compression function 410>
<TBST vine-to-tree function; tbst => rtbst 285>
<TBST main balance function; tbst => rtbst 283>

This code is included in 375.

The only substantative difference for the remaining two functions is that there is no need to set nodes' left tags (since they don't have any):

409. <RTBST tree-to-vine function 409> =
static void 
tree_to_vine (struct rtbst_table *tree) 
{
  struct rtbst_node *p;

  if (tree->rtbst_root == NULL)
    return;

  p = tree->rtbst_root;
  while (p->rtbst_link[0] != NULL)
    p = p->rtbst_link[0];

  for (;;) 
    {
      struct rtbst_node *q = p->rtbst_link[1];
      if (p->rtbst_rtag == RTBST_CHILD) 
        {
          while (q->rtbst_link[0] != NULL)
            q = q->rtbst_link[0];
          p->rtbst_rtag = RTBST_THREAD;
          p->rtbst_link[1] = q;
        }

      if (q == NULL)
        break;

      q->rtbst_link[0] = p;
      p = q;
    }

  tree->rtbst_root = p;
}

This code is included in 408.

410. <RTBST vine compression function 410> =
/* Performs a compression transformation count times, 
   starting at root. */
static void 
compress (struct rtbst_node *root,
          unsigned long nonthread, unsigned long thread) 
{
  assert (root != NULL);

  while (nonthread–) 
    {
      struct rtbst_node *red = root->rtbst_link[0];
      struct rtbst_node *black = red->rtbst_link[0];

      root->rtbst_link[0] = black;
      red->rtbst_link[0] = black->rtbst_link[1];
      black->rtbst_link[1] = red;
      root = black;
    }

  while (thread–) 
    {
      struct rtbst_node *red = root->rtbst_link[0];
      struct rtbst_node *black = red->rtbst_link[0];

      root->rtbst_link[0] = black;
      red->rtbst_link[0] = NULL;
      black->rtbst_rtag = RTBST_CHILD;
      root = black;
    }
}

This code is included in 408.