rb.h File Reference

#include "common.h"
#include "vector.h"
#include "mempool.h"

Go to the source code of this file.

Data Structures
struct	_cp_rbnode
struct	_cp_rbtree

---

Detailed Description

red-black tree definitions. Red-black trees are self balancing binary trees. red-black trees guarantee a O(log n) time for tree operations. An advantage over AVL trees is in that insertion and deletion require a small number of rotations (2 or 3) at the most.

First introduced by Rudolf Bayer in Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms, 1972. The 'red-black' terminology is due to Leo J. Guibas and Robert Sedgewick: A Dichromatic Framework for Balanced Trees, 1978.

Definition in file rb.h.

---

Function Documentation

CPROPS_DLL void cp_rbtree_dump (  cp_rbtree *  tree  )

print tree to stdout Definition at line 1128 of file rb.c.

---