Group PJ_RBTREE

group PJ_RBTREE

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

Defines

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

PJ_RBTREE_SIZE: Guidance on memory required for the tree.

Typedefs

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

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

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

Enums

enum pj_rbcolor_t

Color type for Red-Black tree.

Values:

enumerator PJ_RBCOLOR_BLACK

enumerator PJ_RBCOLOR_RED

Functions

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

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

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

struct pj_rbtree_node

#include <rbtree.h>

The type of the node of the R/B Tree.

Public Members

struct pj_rbtree_node *parent: Pointers to the node’s parent.

struct pj_rbtree_node *left: Pointers to the node’s left sibling.

struct pj_rbtree_node *right: Pointers to the node’s right sibling.

const void *key: Key associated with the node.

void *user_data: User data associated with the node.

pj_rbcolor_t color: The R/B Tree node color.

struct pj_rbtree

#include <rbtree.h>

Declaration of a red-black tree. All elements in the tree must have UNIQUE key. A red black tree always maintains the balance of the tree, so that the tree height will not be greater than lg(N). Insert, search, and delete operation will take lg(N) on the worst case. But for insert and delete, there is additional time needed to maintain the balance of the tree.

Public Members

pj_rbtree_node null_node: Constant to indicate NULL node.

pj_rbtree_node *null: Constant to indicate NULL node.

pj_rbtree_node *root: Root tree node.

unsigned size: Number of elements in the tree.

pj_rbtree_comp *comp: Key comparison function.