www.delorie.com/gnu/docs/avl/libavl_202.html

search

	Buy GNU books!

GNU libavl 2.0.1

12. Right-Threaded AVL Trees

In the same way that we can combine threaded trees with AVL trees to produce threaded AVL trees, we can combine right-threaded trees with AVL trees to produce right-threaded AVL trees. This chapter explores this combination, producing another table implementation.

Here's the form of the source and header files. Notice the use of rtavl_ as the identifier prefix. Likewise, we will often refer to right-threaded AVL trees as "RTAVL trees".

<@xref{\NODE\, , License.>,1} #ifndef RTAVL_H #define @cindex RTAVL_H macro RTAVL_H 1 #include <stddef.h> <@xref{\NODE\, , Table types; tbl =>.> rtavl,14} <@xref{\NODE\, , BST maximum height; bst =>.> rtavl,28} <@xref{\NODE\, , TBST table structure; tbst =>.> rtavl,250} <@xref{\NODE\, , RTAVL node structure.>,417} <@xref{\NODE\, , TBST traverser structure; tbst =>.> rtavl,267} <@xref{\NODE\, , Table function prototypes; tbl =>.> rtavl,15} #endif /* rtavl.h */

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include "rtavl.h" <@xref{\NODE\, , RTAVL functions.>,418}

12.1 Data Types
12.2 Operations
12.3 Rotations
12.4 Insertion
12.5 Deletion
12.6 Copying
12.7 Testing