www.delorie.com/gnu/docs/avl/libavl_242.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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:

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

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include "pavl.h"
&#60;@xref{\NODE\, , PAVL functions.&#62;,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  


  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003