2

I am new to data structures. I have gone through red-black tree insertion algorithm implementation. I am not able to understand, how algorithm takes care of insertion of sorted values.

Let me illustrate with data set [10, 5, 2].

So, Initial 10 will be inserted and will be the root of the tree and its color will be black. 10enter image description here

Next, we'll be adding 5, under root 10. The color of 5 will be red(As of now, It doesn't violate any of the properties). enter image description here

Now, we'll add be adding 2. After addition, the tree will look like :- enter image description here Addition of 2(whose color is red) will violate rule of not allowing red child under red parent. There're 3 cases in Red-black tree :- All the three cases assume that parentOf(newlyInsertedNode) have sibling. But in my case parentOf(2) = 5 doesn't have sibling. So, How this scenario will be dealt in the Red-black tree algorithm.

Mangu Singh Rajpurohit
  • 10,806
  • 4
  • 68
  • 97

1 Answers1

1

The specifics of red-black trees might differ a bit depending on the article/book/implementation.

There, is, however, a very common variant used by Introduction To Algorithms (CLRS). In this variant, there are special NIL children. A NIL child contains a special "Null" key, indicating that it is just a leaf.

The invariants for RB trees are:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

Note, in particular, invariant 3 - NIL nodes are black.

Using this common variant, your RB tree has 4 additional nodes:

  1. the right child of 10

  2. The right child of 5

  3. The left and right children of 2

The right child of 5 is the sibling which you're missing.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185