BLOG | DOCUMENTATION | TRAC

Home --> Documentations --> PJLIB Reference

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_nodepj_rbtree_first (pj_rbtree *tree)
 
pj_rbtree_nodepj_rbtree_last (pj_rbtree *tree)
 
pj_rbtree_nodepj_rbtree_next (pj_rbtree *tree, pj_rbtree_node *node)
 
pj_rbtree_nodepj_rbtree_prev (pj_rbtree *tree, pj_rbtree_node *node)
 
int pj_rbtree_insert (pj_rbtree *tree, pj_rbtree_node *node)
 
pj_rbtree_nodepj_rbtree_find (pj_rbtree *tree, const void *key)
 
pj_rbtree_nodepj_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

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
treethe tree.
nodethe 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
treethe tree.
keythe 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
treethe 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
treethe tree to be initialized.
compkey 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
treethe tree.
nodethe 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
treethe 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
treethe tree.
nodethe 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
treethe tree.
nodethe 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
treethe tree.
nodethe 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
treethe tree.
nodethe node.
Returns
the previous node, or NULL if the node has no previous node.

 


PJLIB Open Source, high performance, small footprint, and very very portable framework
Copyright (C) 2006-2009 Teluu Inc.