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

search

	Buy GNU books!

GNU libavl 2.0.1

13. Right-Threaded Red-Black Trees

This chapter is this book's final demonstration of right-threaded trees, carried out by using them in a red-black tree implementation of tables. The chapter, and the code, follow the pattern that should now be familiar, using rtrb_ as the naming prefix and often referring to right-threaded right-black trees as "RTRB trees".

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

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include "rtrb.h" <@xref{\NODE\, , RTRB functions.>,455}

13.1 Data Types
13.2 Operations
13.3 Insertion
13.4 Deletion
13.5 Testing