14 AVL Trees with Parent Pointers [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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: 

521. <pavl.h 521> =
<Library License 1>
#ifndef PAVL_H
#define PAVL_H 1

#include <stddef.h>

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

#endif /* pavl.h */


522. <pavl.c 522> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "pavl.h"

<PAVL functions 524>