Exercises

The following exercises provide you with the opportunity to practice with red-black trees. The solutions to these exercises are found in the section .

1. Here’s a simple tree:

   

   It’s not supposed to be a red-black tree, don’t worry. However, we can still perform a rotation on it. Show what the tree will look like after you rotate the A and the B.

2. Here’s a red-black tree:

   

   Rotate the 80 and the 100. Don’t worry about violating the Red-Black Rules and having to fix up the tree after the rotation. Simply show what would happen if that one rotation happened to be made.

3. Here’s another red-black tree:

   

   What will the red-black tree look like if you insert a 30? This time, you must follow the entire red-black tree insertion algorithm.

4. This exercise is a continuation of the previous one. Say that after you insert the 30, you then also insert a 20. What will the red-black tree look like when all is said and done?