W

#### Willow Schlanger

domain) of my ranked red-black tree template class.

You can find the latest version here: http://code.google.com/p/options/downloads/list

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

have:

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

delta!!

// and this mapping by order: 0 -> alpha, 1 -> delta

// Now insert "beta" after the "alpha" node and before the "delta!!"

node.

// 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 ->

delta!!

// 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

desired.

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.

Willow