Red-Black Trees

Discussion in 'Mac Programming' started by grapes911, Apr 22, 2006.

  1. Moderator emeritus

    grapes911

    Joined:
    Jul 28, 2003
    Location:
    Citizens Bank Park
    #1
    I have to implement a red-black tree in C++ for a project, but I don't know much about red-black trees. I've been trying to do my research for a few days now, but I still feel pretty lost.

    1. Here is what I know:
    a. They are binary trees.
    b. Every node is either red or black.
    c. The root is black.
    d. Every path from the root to a leaf contains the same number of black nodes.
    e. Red nodes can only have black children.
    f. Every leaf is NULL and black.

    2. Are this properties correct? Are there any other properties that I need to know?

    3. I'm assuming it is more common to use an array rather than pointers. Is this true?

    4. What make a node red or black? And what advantage do I get out of having red and black nodes.

    5. Anyone know of any good sites with good examples?
     
  2. Moderator emeritus

    Mitthrawnuruodo

    Joined:
    Mar 10, 2004
    Location:
    Bergen, Norway
    #2
    Introductions to Algorithms has a whole chapter (13) dedicated to Red-Black threes, but I'm afraid I cannot type in those 30 pages here... :eek:

    Maybe they have the book at your local public library. They don't provide code, but even better, the algorithm in a very easy-to-understand notation.

    I don't think we ever implemented the algorithm in either of my C++ or Java courses...

    Edit: On the other hand, Google is a friend, as ever: http://www.cs.fiu.edu/~weiss/dsaa_c++/code/ ;)
     
  3. macrumors regular

    Joined:
    Apr 6, 2004
    Location:
    canada
    #3
    Is this for a university course?
     
  4. thread starter Moderator emeritus

    grapes911

    Joined:
    Jul 28, 2003
    Location:
    Citizens Bank Park
    #4
    I have some books (none with very good examples). I'm having trouble just understanding the concept, let alone the code. Thank you though.

    Yep.
     
  5. Moderator emeritus

    Mitthrawnuruodo

    Joined:
    Mar 10, 2004
    Location:
    Bergen, Norway
    #5
    Well, that's the brilliant thing about the above mentioned Algorithm book. It explains how the trees work, in detail, with illustrations... :)
     
  6. macrumors 6502a

    Voidness

    Joined:
    Aug 2, 2005
    Location:
    Null
    #6
  7. macrumors 68030

    superbovine

    Joined:
    Nov 7, 2003
    #7
    http://www.ddj.com/184410531

    one of the containers in the STL is a red-black tree (if remember right), anyway if you dig around you can probably find a good example from the stl.
     

Share This Page