Deleting from a TBST - GNU libavl 2.0.2

When we delete a node from a threaded tree, we have to update one or two more pointers than if it were an unthreaded BST. What's more, we sometimes have to go to a bit of effort to track down what pointers these are, because they are in the predecessor and successor of the node being deleted.

The outline is the same as for deleting a BST node:

257. <TBST item deletion function 257> =
void *
tbst_delete (struct tbst_table *tree, const void *item) 
{
  struct tbst_node *p;	/* Node to delete. */
  struct tbst_node *q;	/* Parent of p. */
  int dir;              /* Index into q->tbst_link[] that leads to p. */

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

  <Find TBST node to delete 258>
  <Delete TBST node 259>
  <Finish up after deleting TBST node 266>
}

This code is included in 251.

We search down the tree to find the item to delete, p. As we do it we keep track of its parent q and the direction dir that we descended from it. The initial value of q and dir use the trick seen originally in copying a BST (see Copying a BST Iteratively).

There are nicer ways to do the same thing, though they are not necessarily as efficient. See the exercises for one possibility.

258. <Find TBST node to delete 258> =
if (tree->tbst_root == NULL)
  return NULL;

p = tree->tbst_root;
q = (struct tbst_node *) &tree->tbst_root;
dir = 0;
for (;;) 
  {
    int cmp = tree->tbst_compare (item, p->tbst_data, tree->tbst_param);
    if (cmp == 0) 
      break;

    dir = cmp > 0;
    if (p->tbst_tag[dir] == TBST_THREAD)
      return NULL;

    q = p;
    p = p->tbst_link[dir];
  }
item = p->tbst_data;

This code is included in 257.

The cases for deletion from a threaded tree are a bit different from those for an unthreaded tree. The key point to keep in mind is that a node with n children has n threads pointing to it that must be updated when it is deleted. Let's look at the cases in detail now.

Here's the outline:

259. <Delete TBST node 259> =
if (p->tbst_tag[1] == TBST_THREAD) 
  {
    if (p->tbst_tag[0] == TBST_CHILD)
      { 
        <Case 1 in TBST deletion 260> 
      }
    else 
      { 
        <Case 2 in TBST deletion 261> 
      }
  } 
else 
  {
    struct tbst_node *r = p->tbst_link[1];
    if (r->tbst_tag[0] == TBST_THREAD)
      { 
        <Case 3 in TBST deletion 262> 
      }
    else 
      { 
        <Case 4 in TBST deletion 263> 
      }
  }

This code is included in 257.

Case 1: p has a right thread and a left child

If p has a right thread and a left child, then we replace it by its left child. We also replace its predecessor t's right thread by p's right thread. In the most general subcase, the whole operation looks something like this:

On the other hand, it can be as simple as this:

Both of these subcases, and subcases in between them in complication, are handled by the same code:

260. <Case 1 in TBST deletion 260> =
struct tbst_node *t = p->tbst_link[0];
while (t->tbst_tag[1] == TBST_CHILD)
  t = t->tbst_link[1];
t->tbst_link[1] = p->tbst_link[1];
q->tbst_link[dir] = p->tbst_link[0];

This code is included in 259 and 314.

Case 2: p has a right thread and a left thread

If p is a leaf, then no threads point to it, but we must change its parent q's pointer to p to a thread, pointing to the same place that the corresponding thread of p pointed. This is easy, and typically looks something like this:

There is one special case, which comes up when q is the pseudo-node used for the parent of the root. We can't access tbst_tag[] in this “node”. Here's the code:

261. <Case 2 in TBST deletion 261> =
q->tbst_link[dir] = p->tbst_link[dir];
if (q != (struct tbst_node *) &tree->tbst_root)
  q->tbst_tag[dir] = TBST_THREAD;

This code is included in 259 and 315.

Case 3: p's right child has a left thread

If p has a right child r, and r itself has a left thread, then we delete p by moving r into its place. Here's an example where the root node is deleted:

This just involves changing q's right link to point to r, copying p's left link and tag into r, and fixing any thread that pointed to p so that it now points to r. The code is straightforward:

262. <Case 3 in TBST deletion 262> =
r->tbst_link[0] = p->tbst_link[0];
r->tbst_tag[0] = p->tbst_tag[0];
if (r->tbst_tag[0] == TBST_CHILD) 
  {
    struct tbst_node *t = r->tbst_link[0];
    while (t->tbst_tag[1] == TBST_CHILD)
      t = t->tbst_link[1];
    t->tbst_link[1] = r;
  }
q->tbst_link[dir] = r;

This code is included in 259 and 316.

Case 4: p's right child has a left child

If p has a right child, which in turn has a left child, we arrive at the most complicated case. It corresponds to case 3 in deletion from an unthreaded BST. The solution is to find p's successor s and move it in place of p. In this case, r is s's parent node, not necessarily p's right child.

There are two subcases here. In the first, s has a right child. In that subcase, s's own successor's left thread already points to s, so we need not adjust any threads. Here's an example of this subcase. Notice how the left thread of node 3, s's successor, already points to s.

The second subcase comes up when s has a right thread. Because s also has a left thread, this means that s is a leaf. This subcase requires us to change r's left link to a thread to its predecessor, which is now s. Here's a continuation of the previous example, showing deletion of the new root, node 2:

The first part of the code handles finding r and s:

263. <Case 4 in TBST deletion 263> =
struct tbst_node *s;

for (;;) 
  {
    s = r->tbst_link[0];
    if (s->tbst_tag[0] == TBST_THREAD)
      break;

    r = s;
  }

See also 264 and 265.

This code is included in 259 and 317.

Next, we update r, handling each of the subcases:

264. <Case 4 in TBST deletion 263> +=
if (s->tbst_tag[1] == TBST_CHILD)
  r->tbst_link[0] = s->tbst_link[1];
else 
  {
    r->tbst_link[0] = s;
    r->tbst_tag[0] = TBST_THREAD;
  }

Finally, we copy p's links and tags into s and chase down and update any right thread in s's left subtree, then replace the pointer from q down to s:

265. <Case 4 in TBST deletion 263> +=
s->tbst_link[0] = p->tbst_link[0];
if (p->tbst_tag[0] == TBST_CHILD) 
  {
    struct tbst_node *t = p->tbst_link[0];
    while (t->tbst_tag[1] == TBST_CHILD)
      t = t->tbst_link[1];
    t->tbst_link[1] = s;

    s->tbst_tag[0] = TBST_CHILD;
  }

s->tbst_link[1] = p->tbst_link[1];
s->tbst_tag[1] = TBST_CHILD;

q->tbst_link[dir] = s;

We finish up by deallocating the node, decrementing the tree's item count, and returning the deleted item's data:

266. <Finish up after deleting TBST node 266> =
tree->tbst_alloc->libavl_free (tree->tbst_alloc, p);
tree->tbst_count–;
return (void *) item;

This code is included in 257.

Exercises:

*1. In a threaded BST, there is an efficient algorithm to find the parent of a given node. Use this algorithm to reimplement <Find TBST node to delete 258>. [answer]

2. In case 2, we must handle q as the pseudo-root as a special case. Can we rearrange the TBST data structures to avoid this? [answer]

3. Rewrite case 4 to replace the deleted node's tbst_data by its successor and actually delete the successor, instead of moving around pointers. (Refer back to Exercise 4.8-3 for an explanation of why this approach cannot be used in libavl.) [answer]

*4. Many of the cases in deletion from a TBST require searching down the tree for the nodes with threads to the deleted node. Show that this adds only a constant number of operations to the deletion of a randomly selected node, compared to a similar deletion in an unthreaded tree. [answer]