red black tree insertion

Question

I inserted node 36 in the red black tree and the following red black tree resulted:

my problem is that how to handle double red in this special case? is it case 2 or 3?

Answer 1

Based on Wikipedia's properties and cases...

36 would be inserted under case 5, rotating 22 left.

The parent P is red but the uncle is black or not there.

Wikipedia just says "the uncle is black", but, looking at the code, you'll see that that case triggers.

---

Note that the tree without 36 was already invalid because property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not held:

• 20 to 15 contains 1 black node
• 20 to 30 contains 2 black nodes

Assuming the insert order is 20, 15, 22, 30, 36...

All nodes are inserted as red.

22 would be inserted under case 2.

The parent is black.

30 would be inserted under case 3, making 22 and 15 black and 20 red.

The parent and uncle are red; both are repainted black and the grandparent becomes red.

36 would be inserted under case 5, rotating 22 left.

The parent P is red but the uncle is black or not there.

Answer 2

22 not have a left child

therefore..

case 1: Restructuring

we will left rotation

30 --> root "black"

22--> left child "red"

36--> right child "red"