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: 

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

#include <stddef.h>

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

#endif /* pavl.h */


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

<PAVL functions 522>