Right-Threaded Binary Search Trees

10 Right-Threaded Binary Search Trees

We originally introduced threaded trees to allow for traversal without maintaining a stack explicitly. This worked out well, so we implemented tables using threaded BSTs and AVL and RB trees. However, maintaining the threads can take some time. It would be nice if we could have the advantages of threads without so much of the overhead.

In one common special case, we can. Threaded trees are symmetric: there are left threads for moving to node predecessors and right threads for move to node successors. But traversals are not symmetric: many algorithms that traverse table entries only from least to greatest, never backing up. This suggests a matching asymmetric tree structure that has only right threads.

We can do this. In this chapter, we will develop a table implementation for a new kind of binary tree, called a right-threaded binary search tree, right-threaded tree (see right-threaded tree), or simply “RTBST”, that has threads only on the right side of nodes. Construction and modification of such trees can be faster and simpler than threaded trees because there is no need to maintain the left threads.

There isn't anything fundamentally new here, but just for completeness, here's an example of a right-threaded tree:

Keep in mind that although it is not efficient, it is still possible to traverse a right-threaded tree in order from greatest to least.¹ If it were not possible at all, then we could not build a complete table implementation based on right-threaded trees, because the definition of a table includes the ability to traverse it in either direction (see Manipulators).

Here's the outline of the RTBST code, which uses the prefix rtbst_:

372. <rtbst.h 372> =
<License 1>
#ifndef RTBST_H
#define RTBST_H 1

#include <stddef.h>

<Table types; tbl => rtbst 14>
<TBST table structure; tbst => rtbst 250>
<RTBST node structure 374>
<TBST traverser structure; tbst => rtbst 267>
<Table function prototypes; tbl => rtbst 15>
<BST extra function prototypes; bst => rtbst 88>

#endif /* rtbst.h */

373. <rtbst.c 373> =
<License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "rtbst.h"

<RTBST functions 375>

See also: [Knuth 1997], section 2.3.1.

Exercises:

1. We can define a left-threaded tree (see left-threaded tree) in a way analogous to a right-threaded tree, as a binary search tree with threads only on the left sides of nodes. Is this a useful thing to do? [answer]

Footnotes

[1] It can be efficient if we use a stack to do it, but that kills the advantage of threading the tree. It would be possible to implement two sets of traversers for right-threaded trees, one with a stack, one without, but in that case it's probably better to just use a threaded tree.