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

search

	Buy GNU books!

GNU libavl 2.0.1

16. Red-Black Trees with Parent Pointers

As our twelfth and final example of a table data structure, this chapter will implement a table as a red-black tree with parent pointers, or "PRB" tree for short. We use prb_ as the prefix for identifiers. Here's the outline:

<@xref{\NODE\, , License.>,1} #ifndef PRB_H #define @cindex PRB_H macro PRB_H 1 #include <stddef.h> <@xref{\NODE\, , Table types; tbl =>.> prb,14} <@xref{\NODE\, , RB maximum height; rb =>.> prb,195} <@xref{\NODE\, , TBST table structure; tbst =>.> prb,250} <@xref{\NODE\, , PRB node structure.>,553} <@xref{\NODE\, , TBST traverser structure; tbst =>.> prb,267} <@xref{\NODE\, , Table function prototypes; tbl =>.> prb,15} #endif /* prb.h */

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include "prb.h" <@xref{\NODE\, , PRB functions.>,554}

16.1 Data Types
16.2 Operations
16.3 Insertion
16.4 Deletion
16.5 Testing