www.delorie.com/gnu/docs/avl/libavl_183.html   search  
 
Buy GNU books!


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:

rtbst1

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_:

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

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include "rtbst.h"
&#60;@xref{\NODE\, , RTBST functions.&#62;,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]

11.1 Data Types  
11.2 Operations  
11.3 Search  
11.4 Insertion  
11.5 Deletion  
11.6 Traversal  
11.7 Copying  
11.8 Destruction  
11.9 Balance  
11.10 Testing  


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

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003