In: Computer Science
1. Show the red-black tree that result after successively inserting the keys 1, 2, 5, 15, 4, 7, 8, 14, 11 into an initially empty red-black tree.
Show each step whenever you change a node’s color or make a rotation, mark your operations clearly.
First the Red-Black tree will be empty. Let's start inserting the nodes.
1 - First we will add 1. The resulting tree will look like this.
2 - Now we will add 2.
3 - Now we will add 5.
Now the tree becomes imbalanced, so will do the left rotation to balance it.
4 - Now we will add 15.
5 - Now we will add 4.
6 - Now we will add 7.
7 - Now we will add 8.
8 - Now we will add 14.
Again the tree is not balanced so will do a single left rotation.
9 - Now we will add 11.
The rightmost subtree is not balanced, we will do a right otaion to balace it.
This will be the final tree.
Happy Learning!