4 Replies - 174 Views - Last Post: 09 June 2019 - 08:37 AM

#1 Mavil   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 27-May 19

Red Black trees

Posted 08 June 2019 - 11:15 AM

Hi, i have this question which tells me to color all the nodes of this tree to turn it into a red black tree. The problem is, no matter how i color it i can't seem to get it right according to the red black properties.

Root and Nils are always black
A red node has 2 black children
The amount of black nodes has to be the same on each possible route from the root to all nils.

Attached image(s)

  • Attached Image

Is This A Good Question/Topic? 0
  • +

Replies To: Red Black trees

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12618
  • View blog
  • Posts: 45,778
  • Joined: 27-December 08

Re: Red Black trees

Posted 08 June 2019 - 03:42 PM

Are you allowed to rotate the nodes? If not, then no such coloring exists. Let's walk through the logic.

Left Subtree- It is necessary that (if our tree is a Red-Black Tree) 15 is colored black and 13 is colored red. To see this, we consider the following cases.
  • Suppose 15 is colored red. So the path (19, B) - (15, R)- (N, B) uses two black nodes. Furthermore, as 13 is a child of 15, it must be the case that 13 is colored black. So both paths of the form (19, B) - (15, R) - (13, B) - (N, B) contain three black nodes, contradicting property (3).

  • If instead we color 15 black, the path (19, B) - (15, B) - (N, B) uses three black nodes. By coloring 13 red, the paths of the form (19, B)- (15, B) - (13, R) - (N, B) both use three black nodes. So the left-subtree satisfies the Red-Black tree properties.



Right-Subtree- By a symmetric argument as above, we must color 33 black and 24 red. As 24 is red, 32 must be black. So (19, B)- (33, B)- (24, R) - (32, B)- (N, B) uses four black vertices, contradicting property (3) of a Red-Black Tree.

So this BST is not a Red-Black Tree.

This post has been edited by macosxnerd101: 08 June 2019 - 03:42 PM

Was This Post Helpful? 0
  • +
  • -

#3 Mavil   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 27-May 19

Re: Red Black trees

Posted 09 June 2019 - 02:10 AM

Yes i got to this part too. Left subtree part is easy to understand. In the right subtree, to have the same amount of black nodes that would mean that i'd have to have 24 and 32 colored red which is not possible according to red black tree properties. The only way i see this working as a red black tree is by somehow swapping the 32 and 33 and placing the 33 node to the right of the 32 node and 24 to the left. Then it would be easy to color it.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12618
  • View blog
  • Posts: 45,778
  • Joined: 27-December 08

Re: Red Black trees

Posted 09 June 2019 - 07:58 AM

Red-Black trees balance themselves using rotations. This is done on insertion and removal operations. I would discuss with your instructor to clarify as to whether you should be rotating the tree. I am unsure if your instructor wants you to rotate the tree to transform it into a Red-Black Tree, or if they want you to conclude that this tree is not a Red-Black tree.
Was This Post Helpful? 0
  • +
  • -

#5 Mavil   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 27-May 19

Re: Red Black trees

Posted 09 June 2019 - 08:37 AM

Yea i confirmed with my instructor that i have to rotate the tree. I kinda figured that out before but when i tried it i couldn't make it work, so this time i tried to approach the problem differently. So i start from this:
Attached Image

Obviously i can see that 2 of my nodes on the right tree are red so that's a big nono. What i'm trying to accomplish here is to get the 32 node in the 33's place so i'm trying a different rotation.
Attached Image
Ok, i hope this is correct, i even gave all the NIL nodes numbers to make sure i'm doing this properly. Now i'm trying a final rotation to get my node where i want it and to thus make the tree a redblack tree.
Attached Image
This is what i came up with after i consulted a lot of sources on how to properly do red black rotations. I would like a confirm whether this is correct or i messed up please.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1