10.4 Insertion

Regardless of the kind of binary tree we're dealing with, adding a new node requires setting three pointer fields: the parent pointer and the two child pointers of the new node. On the other hand, we do save a tiny bit on tags: we set either 1 or 2 tags here as opposed to a constant of 3 in <TBST item insertion function 256>.

Here is the outline:

379. <RTBST item insertion function 379> =
void **
rtbst_probe (struct rtbst_table *tree, void *item) 
{
  struct rtbst_node *p; /* Current node in search. */
  int dir;              /* Side of p on which to insert the new node. */

  struct rtbst_node *n; /* New node. */

  <Step 1: Search RTBST for insertion point 380>
  <Step 2: Insert new node into RTBST tree 381>
}

This code is included in 377.

The code to search for the insertion point is not unusual:

380. <Step 1: Search RTBST for insertion point 380> =
if (tree->rtbst_root != NULL)
  for (p = tree->rtbst_root; ; p = p->rtbst_link[dir]) 
    {
      int cmp = tree->rtbst_compare (item, p->rtbst_data, tree->rtbst_param);
      if (cmp == 0)
        return &p->rtbst_data;
      dir = cmp > 0;

      if (dir == 0) 
        {
          if (p->rtbst_link[0] == NULL)
            break;
        } 
      else /* dir == 1 */ 
        {
          if (p->rtbst_rtag == RTBST_THREAD)
            break;
        }
    }
else 
  {
    p = (struct rtbst_node *) &tree->rtbst_root;
    dir = 0;
  }

This code is included in 379.

Now for the insertion code. An insertion to the left of a node p in a right-threaded tree replaces the left link by the new node n. The new node in turn has a null left child and a right thread pointing back to p:

An insertion to the right of p replaces the right thread by the new child node n. The new node has a null left child and a right thread that points where p's right thread formerly pointed:

We can handle both of these cases in one code segment. The difference is in the treatment of n's right child and p's right tag. Insertion into an empty tree is handled as a special case as well:

381. <Step 2: Insert new node into RTBST tree 381> =
n = tree->rtbst_alloc->libavl_malloc (tree->rtbst_alloc, sizeof *n);
if (n == NULL)
  return NULL;

tree->rtbst_count++;
n->rtbst_data = item;
n->rtbst_link[0] = NULL;
if (dir == 0) 
  {
    if (tree->rtbst_root != NULL)
      n->rtbst_link[1] = p;
    else 
      n->rtbst_link[1] = NULL;
  } 
else /* dir == 1 */ 
  {
    p->rtbst_rtag = RTBST_CHILD;
    n->rtbst_link[1] = p->rtbst_link[1];
  }
n->rtbst_rtag = RTBST_THREAD;
p->rtbst_link[dir] = n;

return &n->rtbst_data;

This code is included in 379.