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.

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)

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.

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.

**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.

- 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.

So this BST is not a Red-Black Tree.

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

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.

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.

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:

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.

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.

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.

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.

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.

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.

Page 1 of 1

- Caffeine Lounge
- Corner Cubicle
- Student Campus
- Software Development
- Industry News
- Introduce Yourself
- Nightmare.In.Code

- C and C++
- VB.NET
- Java
- C#
- Python
- PHP
- Mobile Development
- ASP.NET
- .NET Framework
- Ruby
- Game Development
- Assembly
- Databases
- ColdFusion
- VB6
- Other Languages
- 52 Weeks Of Code

- Web Development
- HTML & CSS
- JavaScript
- Graphic Design
- Flash & ActionScript
- Blogging
- SEO & Advertising
- Web Servers & Hosting
- Site Check

- C++ Tutorials
- Java Tutorials
- VisualBasic Tutorials
- VB.NET Tutorials
- C# Tutorials
- PHP Tutorials
- ColdFusion Tutorials
- Database Tutorials

- C Snippets
- C++ Snippets
- Java Snippets
- Visual Basic Snippets
- C# Snippets
- VB.NET Snippets
- ASP.NET Snippets
- PHP Snippets
- Python Snippets
- Ruby Snippets
- ColdFusion Snippets
- SQL Snippets
- Assembly Snippets
- Functional Programming Snippets
- Perl Snippets
- HTML/CSS Snippets
- Javascript Snippets
- Flash/ActionScript Snippets
- ASP Snippets
- Linux, Unix, and Bash Snippets
- Other Languages Snippets
- Regex

Copyright 2001-2020 **MediaGroup1 LLC**, All Rights Reserved

A**MediaGroup1 LLC** Production - Version 6.0.2.1.36

Server: secure3

A

Server: secure3