Harlequin standard Red-Black binary trees

General red-black binary tree routines. More...

Files
file	rbthuff.h
	Huffman code generated from a red-black tree.
file	rbtree.h
	A generally useful Red-Black binary tree implementation.

Detailed Description

General red-black binary tree routines.

A red-black binary tree is the same as an ordinary binary tree, with the extra rules:

1. Every node is either red or black.
2. Every leaf (nil) is black.
3. If a node is red, then both of its children are black.
4. Every simple path from a node to a descendant leaf contains the same number of black nodes (the "black height" is uniform).

Based on the Tome "Introduction to Algorithms" by Cormen, Leiserson and Rivest. A cracking bedtime read.

This implementation allows storage of the key and/or data either in the tree nodes, or as references managed by the caller. Memory allocation and deallocation functions for tree nodes are supplied by the caller (rbt_alloc_fn, rbt_free_fn). A key comparison function (rbt_compare_keys_fn) may be supplied by the caller. Operations to insert, delete, search, navigate, iterate, mutate, and destroy the tree are provided.

A Red-Black tree is represented by an RBT_ROOT structure. This is created and returned by rbt_init(), and destroyed by rbt_dispose(). rbt_init() associates a generic data pointer with the entire tree, this may be retrieved using rbt_get_root_data().

Nodes in the Red-Black tree are represented by RBT_NODE structures. Nodes are allocated and destroyed using separate functions from insertion into and removal from the tree. This allows more efficient re-use of the memory occupied by a node when mutating the key, and also guarantees that insertion will succeed. The rbt_allocate_node() and rbt_free_node() functions may be used to create and destroy nodes that are not attached to a tree. rbt_insert() inserts an unattached node into a tree, and rbt_remove() removes a node from a tree but does not destroy it.

Each node has a key and data, which may be retrieved and set using the rbt_get_node_key(), rbt_set_node_key(), rbt_get_node_data() and rbt_set_node_data() functions. The key must not be modified whilst a node is attached to a tree.

The key and the data may either be stored directly within the RBT_NODE structure, or may be stored by reference. If stored by reference, the caller is responsible for ensuring that the lifetime of the object is at least as long as the tree.

The tree can be tested to determine if it is empty using rbt_is_empty(), or checking if the root node returned by rbt_root_node() is NULL. The rbt_node_count() function will return the number of nodes in a tree.

The rbt_search() function uses the key comparison function supplied when initializing the tree to search for a matching node.

Explicit navigation over a tree is supported by the rbt_root_node(), rbt_minimum(), rbt_maximum(), rbt_predecessor(), and rbt_successor() functions.

Iteration over all elements of a tree is supported by the rbt_walk() function, using a callback function (rbt_callback_fn) supplied by the caller to visit each node. Mutation of the tree is not supported by this function, however it can stop the iteration early.