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

search

	Buy GNU books!

GNU libavl 2.0.1

15. AVL Trees with Parent Pointers

This chapter adds parent pointers to AVL trees. The result is a data structure that combines the strengths of AVL trees and trees with parent pointers. Of course, there's no free lunch: it combines their disadvantages, too.

The abbreviation we'll use for the term "AVL tree with parent pointers" is "PAVL tree", with corresponding prefix pavl_. Here's the outline for the PAVL table implementation:

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

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include "pavl.h" <@xref{\NODE\, , PAVL functions.>,522}

15.1 Data Types
15.2 Rotations
15.3 Operations
15.4 Insertion
15.5 Deletion
15.6 Traversal
15.7 Copying
15.8 Testing