How to use release 4 of my public domain ranked red-black treetemplate class.


Willow Schlanger

I just released version 4 (an improved rewrite, now in the public
domain) of my ranked red-black tree template class.

You can find the latest version here:

Basically, a ranked red-black tree is similar to the STL "map"
container except if you have the mapping
0 -> a
1 -> b
2 -> c

And then you insert an item before position 0 with value 'd', we now
0 -> d
1 -> a
2 -> b
3 -> c

This is done in logarithmic time, i.e. I don't have to go through all
nodes in the tree and update their key; that is done automatically
through implicit keys.

Nodes in the ranked red-black tree have a weight, normally 1.

The "order" (also known as rank) of a node equals the number of nodes
that precede it via an in-order traversal.
The "span" of a node is the sum of the weights of all nodes that
precede it via an in-order traversal.
The weight of a non-NULL node must be at least 1, or else we would
have multiple nodes with the same "key" (span).

// Create a new ranked red-black tree, whose values are of type const
char *.
RrbTree<const char *> t;

// Insert two nodes, "alpha" and "delta!!". We assign a weight equal
to the length of the string to each node.
// First, we insert the "alpha" node at span 0, i.e. the beginning.
// Then, we insert "delta!!" at span 5, i.e. after "alpha".
RrbNode *alpha = t.insertBySpan(0, "alpha", 5);
RrbNode *delta = t.insertBySpan(5, "delta!!", 7);

// At this point we have this mapping by span: 0 -> alpha, 5 ->
// and this mapping by order: 0 -> alpha, 1 -> delta
// Now insert "beta" after the "alpha" node and before the "delta!!"
// Before, we inserted by "span". Now, we insert by "order". This
means that after
// the following statement executes, "beta" will have order 1.
RrbNode *beta = t.insertByOrder(1, "beta", 4);

// We now have this mapping by span: 0 -> alpha, 5 -> beta, 9 ->
// and this mapping by order: 0 -> alpha, 1 -> beta, 2 -> delta

std::cout << (*alpha).getOrder() << std::endl; // prints 0
std::cout << (*beta).getOrder() << std::endl; // prints 1
std::cout << (*delta).getWeightedPosition() << std::endl; // prints
the span to delta, i.e. 9

// Given a node, you can use node->next() or node->prev() to find the
successor or predecessor.
// Dereferencing a node returns its value, which can be changed if
std::cout << **(alpha->next()) << std::endl; // prints "beta"

// The following will change "alpha" to "xx":
**alpha = "xx"; // change the value of the alpha node
alpha->setWeight(2); // update the weight of alpha, length of the xx
node is now 2

// Remove delta from the tree.
t.removeByOrder(2); // the node at order 2 is "delta"

// We now have the following order map: 0 -> xx, 1 -> beta
// and the following span map: 0 -> xx, 2 -> beta

All of the above operations have logarithmic time!!

Hopefully I didn't make any mistakes, and hopefully someone will find
this useful.


Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question