7.6 Insertion

It take a little more effort to insert a new node into a threaded BST than into an unthreaded one, but not much more. The only difference is that we now have to set up the new node's left and right threads to point to its predecessor and successor, respectively.

Fortunately, these are easy to figure out. Suppose that new node n is the right child of its parent p (the other case is symmetric). This means that p is n's predecessor, because n is the least node in p's right subtree. Moreover, n's successor is the node that was p's successor before n was inserted, that is to say, it is the same as p's former right thread.

Here's an example that may help to clear up the description. When new node 3 is inserted as the right child of 2, its left thread points to 2 and its right thread points where 2's right thread formerly did, to 4:

The following code unifies the left-side and right-side cases using dir, which takes the value 1 for a right-side insertion, 0 for a left-side insertion. The side opposite dir can then be expressed simply as !dir.

256. <TBST item insertion function 256> =
void **
tbst_probe (struct tbst_table *tree, void *item) 
{
  struct tbst_node *p; /* Traverses tree to find insertion point. */
  struct tbst_node *n; /* New node. */
  int dir;             /* Side of p on which n is inserted. */

  assert (tree != NULL && item != NULL);

  <Step 1: Search TBST for insertion point 257>
  <Step 2: Insert TBST node 258>

  return &n->tbst_data;
}

This code is included in 253.

257. <Step 1: Search TBST for insertion point 257> =
if (tree->tbst_root != NULL)
  for (p = tree->tbst_root; ; p = p->tbst_link[dir]) 
    {
      int cmp = tree->tbst_compare (item, p->tbst_data, tree->tbst_param);
      if (cmp == 0)
        return &p->tbst_data;
      dir = cmp > 0;

      if (p->tbst_tag[dir] == TBST_THREAD)
        break;
    }
else 
  {
    p = (struct tbst_node *) &tree->tbst_root;
    dir = 0;
  }

This code is included in 256 and 670.

258. <Step 2: Insert TBST node 258> =
n = tree->tbst_alloc->libavl_malloc (tree->tbst_alloc, sizeof *n);
if (n == NULL)
  return NULL;

tree->tbst_count++;
n->tbst_data = item;
n->tbst_tag[0] = n->tbst_tag[1] = TBST_THREAD;
n->tbst_link[dir] = p->tbst_link[dir];
if (tree->tbst_root != NULL) 
  {
    p->tbst_tag[dir] = TBST_CHILD;
    n->tbst_link[!dir] = p;
  }
else 
  n->tbst_link[1] = NULL;
p->tbst_link[dir] = n;

This code is included in 256, 305, and 341.

See also:  [Knuth 1997], algorithm 2.3.1I.

Exercises:

1. What happens if we reverse the order of the final if statement above and the following assignment? [answer]