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:

410. <RTBST balance function 410> =
<RTBST tree-to-vine function 411>
<RTBST vine compression function 412>
<TBST vine-to-tree function; tbst => rtbst 287>
<TBST main balance function; tbst => rtbst 285>

This code is included in 377.

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):

411. <RTBST tree-to-vine function 411> =
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 410.

412. <RTBST vine compression function 412> =
/* 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 410.