# Red/Black Trees

• 12-11-2010, 09:06 PM
f1gh
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

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)
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:
Code:

```                    45 - black                 /    \               5-blk  50-blk             /        /           1-red  10 - red```
thanks.
• 12-12-2010, 12:11 AM
f1gh
- i am sure someone here can verify this ;)
• 12-12-2010, 01:30 AM
• 12-12-2010, 01:45 AM
f1gh
thanks for the link; its pretty awesome :D

it came up with
Code:

```                        45 -black                     /      \                 5 - black 50-black             /    \         1-red  10-red```
which is different from my ending result
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
• 12-12-2010, 03:30 AM