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

Discussion in 'C++' started by Willow Schlanger, Nov 27, 2010.

  1. 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, Nov 27, 2010
    #1
    1. Advertising

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

    On Nov 26, 11:29 pm, Willow Schlanger <> wrote:
    > 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
     
    Willow Schlanger, Nov 27, 2010
    #2
    1. Advertising

  3. Willow Schlanger

    Jorgen Grahn Guest

    On Sat, 2010-11-27, Willow Schlanger wrote:
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Nov 27, 2010
    #3
  4. On Nov 27, 2:56 am, Jorgen Grahn <> wrote:
    > On Sat, 2010-11-27, Willow Schlanger wrote:
    > > 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


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

    Willow
     
    Willow Schlanger, Dec 28, 2010
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Thomas

    Red Black Tree!!!

    Thomas, Feb 20, 2004, in forum: C++
    Replies:
    6
    Views:
    6,354
    Claudio Puviani
    Feb 20, 2004
  2. Just Another Victim of the Ambient Morality

    I'm looking for a pythonic red-black tree...

    Just Another Victim of the Ambient Morality, Dec 15, 2006, in forum: Python
    Replies:
    5
    Views:
    389
    Stuart D. Gathman
    Dec 16, 2006
  3. Fei Liu
    Replies:
    11
    Views:
    3,196
    Fei Liu
    Jun 29, 2007
  4. Willow Schlanger
    Replies:
    0
    Views:
    445
    Willow Schlanger
    Dec 28, 2010
  5. Dan Stromberg

    Red Black Tree implementation?

    Dan Stromberg, May 2, 2013, in forum: Python
    Replies:
    14
    Views:
    324
    duncan smith
    May 12, 2013
Loading...

Share This Page