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


GNU libavl 2.0.1

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

9. Threaded AVL Trees

The previous chapter introduced a new concept in BSTs, the idea of threads. Threads allowed us to simplify traversals and eliminate the use of stacks. On the other hand, threaded trees can still grow tall enough that they reduce the program's performance unacceptably, the problem that balanced trees were meant to solve. Ideally, we'd like to add threads to balanced trees, to produce threaded balanced trees that combine the best of both worlds.

We can do this, and it's not even very difficult. This chapter will show how to add threads to AVL trees. The next will show how to add them to red-black trees.

Here's an outline of the table implementation for threaded AVL or "TAVL" trees that we'll develop in this chapter. Note the usage of prefix tavl_ for these functions.

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

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include "tavl.h"
&#60;@xref{\NODE\, , TAVL functions.&#62;,300}

9.1 Data Types  
9.2 Rotations  
9.3 Operations  
9.4 Insertion  
9.5 Deletion  
9.6 Copying  
9.7 Testing  


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