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   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003