Determine node colour in Red Black Tree

Question

I was reading about Red Black Trees, and I understand that nodes can either be red or black. The rules say:

1) Every node has a color - either red or black.

2) Root of tree is always black.

3) There are no two adjacent red nodes (A red node cannot have a red parent or red child)

4) Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

There is no description of what nodes should be coded as red? I understand that the tree can have all black nodes, but what I don't understand is that when should we mark a node as red?

I would also like to understand the reasoning behind this colour coding. I know that an RB tree is basically a self-balancing tree, but I want to understand how this binary colour coding helps in that?

SoronelHaetir SoronelHaetir · Accepted Answer · 2020-06-13T21:20:46

The usual way is to color all nodes red on insert then perform a fix-up, inserting a red node may not produce any violation at all but inserting a black node always would.

Basic insert algorithm:

insert value as for any BST, coloring the node red if a new node is created, done if the value is already present
LOOP:
if node is tree anchor then set node's color to black and done
if node's parent's color is black then done
if node's uncle's color is red then flip colors of node's parent, node's uncle and node's grandparent, set node to node's grandparent and go to LOOP
if node's parent and node have different orientations then rotate node's parent so that node's parent becomes child to node
otherwise set node to node's parent
flip colors of node and node's parent
rotate at node's parent so that node's parent becomes child to node
done

Determine node colour in Red Black Tree

1 Answers