Announce: C++ source for a ranked red-black tree

[Willow Schlanger]

Hi,

I just finished implementing (but not testing!) a red-black tree based
on the awesome public domain tutorial found here:
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

I had to rework that code to do what I wanted. Normal red-black trees
explicitly store a key at each node. This works for storing phone
numbers but supposed the application is a text editor where the "key"
is a line number and the value is associated information for that
line. Then suppose we insert a new line at the beginning! The effect
of this is to "shift" all other keys, i.e. to insert a new value with
a key of 0 and to increase all other keys by 1.

My "Ranked" Red-Black tree does not explicitly store keys, but instead
stores a "weight" (normally 1) for each node and a "span". The span of
a node equals that node's weight plus the span of the node's children.
The span of a node cannot be less than its weight, and weights for non-
NULL nodes must be at least 1. A NULL node has a weight (and span) of
0.

Now given a node, we can say, "what is your position?" If all weights
are 1, then this is the "rank" of the node, i.e. the implicit key, or
the number of nodes that precede it in an in-order traversal of the
binary tree. The true definition of position is: the sum of all
weights for all nodes that precede the node in question in an in-order
traversal.

We can also find a node based on its position.

If we have to change a weight, i.e. if a line becomes longer or
shorter, this can be done in logarithmic time.

Normally a text editor would use two "ranked" red-black trees for high
efficiency. The document contents would be stored in an STL
"rope" (SGI extension). Both ranked red black trees have one entry per
line.

The first ranked red-black tree stores information associated with
each line, and has a weight equal to the weight of the line of text.

The second ranked red-black tree stores a pointer to a node in the
second ranked red-black tree and each node here has a weight of one.

Given a line number, we can then determine the number of characters
that precede that line in the rope. This is useful, because that is
the start offset into the rope for the line, i.e. for displaying the
line.

What we can then do in logarithmic time:
1. Insert a line, anywhere.
2. Look up a line by line number, to determine the # characters that
precede the line (i.e. buffer offset)
3. Delete a line, anywhere.
4. Change the length of a line.
5. Given a node (i.e. stored by a bookmark or cursor position), we can
determine the line number

I hope someone out there can find an application for this besides a
text editor. The gist of it is, it's a red-black tree where the "key"
is implicitly defined to be the sum of all weights for all nodes that
precede the node in question in an in-order traversal.

Thus, if I insert something at position 0, that node now has a "key"
of 0. Now if I insert another node at position 0, the key of the first
node becomes 1 and the new node's key is now 0. Likewise for deleting
nodes, if I delete a node then all other nodes after it have their key
automatically subtracted by the weight of the node that was just
deleted.

While two red-black trees of the usual kind can be used to accomplish
this, the complexity would be perhaps N log(N) for most operations
which is worse than linear time. My method (which probably was
invented decades ago by really smart people) does these operations in
linear time.

You can find the latest version of the ranked red-black tree here:
http://code.google.com/p/options/downloads/list

 

[Willow Schlanger]

Whoops, it's getting late, some typo corrections are below...

Hi, [snip]
Normally a text editor would use two "ranked" red-black trees for high
efficiency. The document contents would be stored in an STL
"rope" (SGI extension). Both ranked red black trees have one entry per
line.

The first ranked red-black tree stores information associated with
each line, and has a weight equal to the weight of the line of text.

This should read:
The first ranked red-black tree stores information associated with
each
line, and has a weight equal to the length of the line of text.

The second ranked red-black tree stores a pointer to a node in the
second ranked red-black tree and each node here has a weight of one.

This should read: the second ranked red-black tree stores a pointer to
a node in the first red-black tree and each node here has a weight of
one.

[snip]

While two red-black trees of the usual kind can be used to accomplish
this, the complexity would be perhaps N log(N) for most operations
which is worse than linear time. My method (which probably was
invented decades ago by really smart people) does these operations in
linear time.

Oops, I meant my method does all these operations in LOGARITHMIC time.

You can find the latest version of the ranked red-black tree here:http://code.google.com/p/options/downloads/list

Willow

 

[Jorgen Grahn]

Hi,

I just finished implementing (but not testing!) a red-black tree based
on the awesome public domain tutorial found here:
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx ....
You can find the latest version of the ranked red-black tree here:
http://code.google.com/p/options/downloads/list

RankedRedBlackTree t;
void *sir = t.insert(0, (void *)("sir"));
std::cout << "pos(sir) = " << t.getPosition(sir) << std::endl;

You should also have looked at the tree implementation behind your standard
library's std::map. I would personally never use a tree which could store only
void pointers.

/Jorgen

 

[Willow Schlanger]

  RankedRedBlackTree t;
  void *sir = t.insert(0, (void *)("sir"));
  std::cout << "pos(sir) = " << t.getPosition(sir) << std::endl;

You should also have looked at the tree implementation behind your standard
library's std::map.  I would personally never use a tree which could store only
void pointers.

/Jorgen

I just did the fourth release. It uses template's now, so you can
store anything you want to !

Willow