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.

Returns

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.

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.