www.delorie.com/gnu/docs/avl/libavl_183.html search
GNU libavl 2.0.1

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

# 11. 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.(14) 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 section 3.10.2 Manipulators).

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

 ```<@xref{\NODE\, , License.>,1} #ifndef RTBST_H #define @cindex RTBST_H macro RTBST_H 1 #include <stddef.h> <@xref{\NODE\, , Table types; tbl =>.> rtbst,14} <@xref{\NODE\, , TBST table structure; tbst =>.> rtbst,250} <@xref{\NODE\, , RTBST node structure.>,374} <@xref{\NODE\, , TBST traverser structure; tbst =>.> rtbst,267} <@xref{\NODE\, , Table function prototypes; tbl =>.> rtbst,15} <@xref{\NODE\, , BST extra function prototypes; bst =>.> rtbst,88} #endif /* rtbst.h */ ```

 ```<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include "rtbst.h" <@xref{\NODE\, , RTBST functions.>,375} ```