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.

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

#include <stddef.h>

<Table types; tbl => tavl 14>
<BST maximum height; bst => tavl 28>
<TBST table structure; tbst => tavl 250>
<TAVL node structure 299>
<TBST traverser structure; tbst => tavl 267>
<Table function prototypes; tbl => tavl 15>

#endif /* tavl.h */

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

<TAVL functions 300>