If I add the following in this order into a red-black tree:
tree.Put(7)
tree.Put(3)
tree.Put(1)
7 3
/ rotate(3) /
3 -----> 1 7
/
1
should I perform a right rotation after the insertion of 1 ?
I am reading the algorithms bible but it the pseudocode doesn’t indicate what to do.
7
At the root, 7 is black. After inserting the 3, it is red (because all inserted nodes are reds).
When you insert the 1, it is also red, so you have violated one property (the son of a red node must be black). Since you also need to maintain the fact that all paths have the same number of black nodes, you cannot simply color the 3 in black.
So you need to perform a rotation.
After checking the book: I believe this is case 3: color the grandparent red & perform right rotation.
0