Results 1 to 5 of 5

Thread: Red/Black Trees

  1. #1
    f1gh is offline Member
    Join Date
    Nov 2010
    Posts
    46
    Rep Power
    0

    Default Red/Black Trees

    This is end of chapter review excercise i am doing on my own to practice. I want to know if this is a valid representation of a Red/black Trees:
    rules of a red black tree:
    a) root has to be black
    b) all children of a red node are black
    c) Every path from root to a leaf contains has same number of a black nodes

    so prob. is start with empty red/black tree:
    insert(40); insert(25); insert(10); insert(5); insert(1); insert(45); insert(50);

    my representation of this is (after re-balancing and changing colors)
    Java Code:
                                     45 - black
                                  /               \
                               40 - red         50 - black
                               /                 /
                             5-black        25 - red
                          /     \
                     1-red  10 - red
    i believe this is correct but just need verification to ensure my practice answer is correct (no solutions provided in book. This IS NOT DUE for homework just practicing for my final).

    After creating tree i have 2 more things to do: remove(40); remove(25)
    again my implementation after rebalancing and changing colors:
    Java Code:
                        45 - black
                     /     \
                  5-blk   50-blk
                 /         / 
               1-red   10 - red
    thanks.

  2. #2
    f1gh is offline Member
    Join Date
    Nov 2010
    Posts
    46
    Rep Power
    0

    Default

    - i am sure someone here can verify this ;)

  3. #3
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    6

  4. #4
    f1gh is offline Member
    Join Date
    Nov 2010
    Posts
    46
    Rep Power
    0

    Default

    thanks for the link; its pretty awesome :D

    it came up with
    Java Code:
                            45 -black
                        /      \
                    5 - black 50-black
                /     \
             1-red   10-red
    which is different from my ending result
    Java Code:
                        45 - black
                     /     \
                  5-blk   50-blk
                 /         / 
               1-red   10 - red
    i understand how red/back trees are constructed. What i need to know is that is my answer correct even though it varies from the demo output(i feel mine is correct because it doesn't violate any rules of red/black trees). And that is really what i needed someone to verify for me as i know there are multiple ways to do same thing.

    still thanks though.
    oh and if someone needs to see demo for AVL Trees, go here:
    http://www.site.uottawa.ca/~stan/csi...ts/avl/BT.html
    Last edited by f1gh; 12-12-2010 at 01:13 AM. Reason: posted link for avl trees.

  5. #5
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    6

    Default

    Yeah no problem, been too long since I implemented a RB tree form me to say comfortably, but since you can follow the rules and sometimes shift either right or left depending on how you coded, you could in theory get different results. However, I remember in my class back in the day, there was only one result, perhaps because we tested based on the specific algorithm used in our text?

Similar Threads

  1. red black tree
    By ahmakki in forum New To Java
    Replies: 1
    Last Post: 03-21-2010, 06:49 AM
  2. Help required for black berry app development
    By khadaree in forum CLDC and MIDP
    Replies: 0
    Last Post: 03-08-2010, 11:04 AM
  3. Red Black tree insertion
    By unicorn in forum New To Java
    Replies: 16
    Last Post: 11-03-2009, 05:46 PM
  4. Why this image background is black ?
    By samson in forum Java 2D
    Replies: 1
    Last Post: 07-17-2007, 04:24 AM
  5. Implementing a red-black tree in java
    By baltazar in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 08:37 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •