8 Threaded AVL Trees [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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. 

299. <tavl.h 299> =
<Library License 1>
#ifndef TAVL_H
#define TAVL_H 1

#include <stddef.h>

<Table types; tbl => tavl 15>
<BST maximum height; bst => tavl 29>
<TBST table structure; tbst => tavl 252>
<TAVL node structure 301>
<TBST traverser structure; tbst => tavl 269>
<Table function prototypes; tbl => tavl 16>

#endif /* tavl.h */


300. <tavl.c 300> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "tavl.h"

<TAVL functions 302>