Illustration 1: Tree - Generated from http://people.ksp.sk/~kuko/bak/
Illustration 2: RBTree - Generated from
As shown in the illustration 1 and 2, tree generated
by rbtree is better and efficient.
Coming back to the implementation, there are a lot
of interesting things we can do with the rbtree. One of the basic and
the most useful complex data structure can be an array wherein any
new element that is added is numbered serially thus we get
flexibility of adding or removing elements easily without having to
work on a fixed range. For example when we add first element its
index automatically becomes 1, the consecutive element is numbered 2
and so on. Whenever an element is to removed all the elements with
higher indexes can be renumbered thus reordering the complex array.
Secondly, keys can be based on the strings
themselves thus we can implement hash tables based on strings wherein
a group of elements can be inserted with a string identifier.
All of these functions are available in the rbtree
class of the NeweraHPC library(available at http://newerahpc.googlecode.com).
The library works in the following modes:
NHPC_RBTREE_NUM is the simple mode where numeric
keys are used.
NHPC_RBTREE_STR uses strings as keys.
NHPC_RBTREE_NUM_MANAGED uses numeric keys and
recalculates keys when an element is removed from the list. It can be
used as an array.
NHPC_RBTREE_NUM_HASH works like a hash table under a
Using the rbtree class is very simple.
It can be initialized by rbtree_t(mode);
Element can be inserted by object.insert(parameters)
Element can be removed by object.erase(paramaters)
Element can be searched by object.search(paramaters)
*Parameters depend upon the mode of the rbtree.