Question

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.

Answer 1

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!