Red/Black Balanced Tree [Data Structure.]

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
Defines
#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) ).

---

Define Documentation

#define PJ_RBTREE_NODE_SIZE   (sizeof(pj_rbtree_node))

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

#define PJ_RBTREE_SIZE   (sizeof(pj_rbtree))

Guidance on memory required for the tree.

---

Typedef Documentation

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

enum pj_rbcolor_t

Color type for Red-Black tree.

---

Function Documentation

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_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_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.

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.

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_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.

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)

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_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_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.