www.delorie.com/gnu/docs/avl/libavl_188.html

search

	Buy GNU books!

GNU libavl 2.0.1

11.5 Deletion

Deleting a node from an RTBST can be done using the same ideas as for other kinds of trees we've seen. However, as it turns out, a variant of this usual technique allows for faster code. In this section, we will implement the usual method, then the improved version. The latter is actually used in libavl.

Here is the outline of the function. Step 2 is the only part that varies between versions:

void * rtbst_delete (struct rtbst_table *tree, const void *item) { struct rtbst_node *p; /* Node to delete. */ struct rtbst_node *q; /* Parent of p. */ int dir; /* Index into q->rtbst_link[] that leads to p. */ assert (tree != NULL && item != NULL); <@xref{\NODE\, , Step 1: Find RTBST node to delete.>,381} <@xref{left-looking, , Step 2: Delete RTBST node.>,388} <@xref{\NODE\, , Step 3: Finish up after deleting RTBST node.>,382} }

This code is included in @refalso{375

The first step just finds the node to delete. After it executes, p is the node to delete and q and dir are set such that q->rtbst_link[dir] == p.

if (tree->rtbst_root == NULL) return NULL; p = tree->rtbst_root; q = (struct rtbst_node *) &tree->rtbst_root; dir = 0; if (p == NULL) return NULL; for (;;) { int cmp = tree->rtbst_compare (item, p->rtbst_data, tree->rtbst_param); if (cmp == 0) break; dir = cmp > 0; if (dir == 0) { if (p->rtbst_link[0] == NULL) return NULL; } else /* dir == 1 */ { if (p->rtbst_rtag == RTBST_THREAD) return NULL; } q = p; p = p->rtbst_link[dir]; } item = p->rtbst_data;

This code is included in @refalso{380

The final step is also common. We just clean up and return:

tree->rtbst_alloc->libavl_free (tree->rtbst_alloc, p); tree->rtbst_count--; return (void *) item;

This code is included in @refalso{380

11.5.1 Right-Looking Deletion
11.5.2 Left-Looking Deletion
11.5.3 Aside: Comparison of Deletion Algorithms