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

GNU libavl 2.0.1

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

8. Threaded Binary Search Trees

Traversal in inorder, as done by libavl traversers, is a common operation in a binary tree. To do this efficiently in an ordinary binary search tree or balanced tree, we need to maintain a list of the nodes above the current node, or at least a list of nodes still to be visited. This need leads to the stack used in struct bst_traverser and friends.

It's really too bad that we need such stacks for traversal. First, they take up space. Second, they're fragile: if an item is inserted into or deleted from the tree during traversal, or if the tree is balanced, we have to rebuild the traverser's stack. In addition, it can sometimes be difficult to know in advance how tall the stack will need to be, as demonstrated by the code that we wrote to handle stack overflow.

These problems are important enough that, in this book, we'll look at two different solutions. This chapter looks at the first of these, which adds special pointers, each called a thread (see thread), to nodes, producing what is called a threaded binary search tree, threaded tree (see threaded tree), or simply a TBST.(13) Later in the book, we'll examine an alternate and more general solution using a parent pointer (see parent pointer) in each node.

Here's the outline of the TBST code. We're using the prefix tbst_ this time:

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

&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include "tbst.h"
&#60;@xref{\NODE\, , TBST functions.&#62;,251}

8.1 Threads  
8.2 Data Types  
8.3 Operations  
8.4 Creation  
8.5 Search  
8.6 Insertion  
8.7 Deletion  
8.8 Traversal  
8.9 Copying  
8.10 Destruction  
8.11 Balance  
8.12 Testing  

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

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