Red/Black Balanced Tree

Red/Black tree is the variant of balanced tree, where the search, insert, and delete operation is guaranteed to take at most O( lg(n) ). More...

Data Structures
struct	pj_rbtree_node
struct	pj_rbtree

Macros
#define	PJ_RBTREE_NODE_SIZE   (sizeof(pj_rbtree_node))
#define	PJ_RBTREE_SIZE   (sizeof(pj_rbtree))

Typedefs
typedef int	pj_rbtree_comp(const void *key1, const void *key2)

Enumerations
enum	pj_rbcolor_t { PJ_RBCOLOR_BLACK , PJ_RBCOLOR_RED }

Functions
void	pj_rbtree_init (pj_rbtree *tree, pj_rbtree_comp *comp)
pj_rbtree_node *	pj_rbtree_first (pj_rbtree *tree)
pj_rbtree_node *	pj_rbtree_last (pj_rbtree *tree)
pj_rbtree_node *	pj_rbtree_next (pj_rbtree *tree, pj_rbtree_node *node)
pj_rbtree_node *	pj_rbtree_prev (pj_rbtree *tree, pj_rbtree_node *node)
int	pj_rbtree_insert (pj_rbtree *tree, pj_rbtree_node *node)
pj_rbtree_node *	pj_rbtree_find (pj_rbtree *tree, const void *key)
pj_rbtree_node *	pj_rbtree_erase (pj_rbtree *tree, pj_rbtree_node *node)
unsigned	pj_rbtree_max_height (pj_rbtree *tree, pj_rbtree_node *node)
unsigned	pj_rbtree_min_height (pj_rbtree *tree, pj_rbtree_node *node)

Detailed Description

Red/Black tree is the variant of balanced tree, where the search, insert, and delete operation is guaranteed to take at most O( lg(n) ).

Macro Definition Documentation

PJ_RBTREE_NODE_SIZE

#define PJ_RBTREE_NODE_SIZE   (sizeof(pj_rbtree_node))

Guidance on how much memory required for each of the node.

PJ_RBTREE_SIZE

#define PJ_RBTREE_SIZE   (sizeof(pj_rbtree))

Guidance on memory required for the tree.

Typedef Documentation

pj_rbtree_comp

typedef int pj_rbtree_comp(const void *key1, const void *key2)

The type of function use to compare key value of tree node.

Returns

0 if the keys are equal <0 if key1 is lower than key2 >0 if key1 is greater than key2.

Enumeration Type Documentation

pj_rbcolor_t

enum pj_rbcolor_t

Color type for Red-Black tree.

Function Documentation

pj_rbtree_erase()

pj_rbtree_node * pj_rbtree_erase	(	pj_rbtree *	tree,
		pj_rbtree_node *	node
	)

Erase a node from the tree.

Parameters

tree	the tree.
node	the node to be erased.

Returns

the tree node itself.

pj_rbtree_find()

pj_rbtree_node * pj_rbtree_find	(	pj_rbtree *	tree,
		const void *	key
	)

Find a node which has the specified key.

Parameters

tree	the tree.
key	the key to search.

Returns

the tree node with the specified key, or NULL if the key can not be found.

pj_rbtree_first()

pj_rbtree_node * pj_rbtree_first

(

pj_rbtree *

tree

)

Get the first element in the tree. The first element always has the least value for the key, according to the comparison function.

Parameters

tree

the tree.

Returns

the tree node, or NULL if the tree has no element.

pj_rbtree_init()

void pj_rbtree_init	(	pj_rbtree *	tree,
		pj_rbtree_comp *	comp
	)

Initialize the tree.

Parameters

tree	the tree to be initialized.
comp	key comparison function to be used for this tree.

pj_rbtree_insert()

int pj_rbtree_insert	(	pj_rbtree *	tree,
		pj_rbtree_node *	node
	)

Insert a new node. The node will be inserted at sorted location. The key of the node must be UNIQUE, i.e. it hasn't existed in the tree.

Parameters

tree	the tree.
node	the node to be inserted.

Returns

zero on success, or -1 if the key already exist.

pj_rbtree_last()

pj_rbtree_node * pj_rbtree_last

(

pj_rbtree *

tree

)

Get the last element in the tree. The last element always has the greatest key value, according to the comparison function defined for the tree.

Parameters

tree

the tree.

Returns

the tree node, or NULL if the tree has no element.

pj_rbtree_max_height()

unsigned pj_rbtree_max_height	(	pj_rbtree *	tree,
		pj_rbtree_node *	node
	)

Get the maximum tree height from the specified node.

Parameters

tree	the tree.
node	the node, or NULL to get the root of the tree.

Returns

the maximum height, which should be at most lg(N)

pj_rbtree_min_height()

unsigned pj_rbtree_min_height	(	pj_rbtree *	tree,
		pj_rbtree_node *	node
	)

Get the minumum tree height from the specified node.

Parameters

tree	the tree.
node	the node, or NULL to get the root of the tree.

Returns

the height

pj_rbtree_next()

pj_rbtree_node * pj_rbtree_next	(	pj_rbtree *	tree,
		pj_rbtree_node *	node
	)

Get the successive element for the specified node. The successive element is an element with greater key value.

Parameters

tree	the tree.
node	the node.

Returns

the successive node, or NULL if the node has no successor.

pj_rbtree_prev()

pj_rbtree_node * pj_rbtree_prev	(	pj_rbtree *	tree,
		pj_rbtree_node *	node
	)

The the previous node for the specified node. The previous node is an element with less key value.

Parameters

tree	the tree.
node	the node.

Returns

the previous node, or NULL if the node has no previous node.