Balanced Trees
Red-Black trees

Exercises

9. Which of the follow are legal balanced red-black BSTs?Solution. (iii) and (iv) only. (i) is not balanced, (ii) is not in symmetric order or balanced.
13. True or false: If you insert keys in increasing order into a red-black BST, the tree height is monotonically increasing.Solution. True, see the next question.
14. Draw the red-black BST that results when you insert letters A through K in order into an initially empty red-black BST. Then, describe what happens in general when red-black BSTs are built by inserting keys in ascending order.
    

    Insert 255 keys in a red-black BST in ascending order.

    Your browser can not display this movie.
    Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.

15. Answer the previous two questions for the case when the keys are inserted in descending order.Solution. False.
    

    Insert 255 keys in a red-black BST in descending order.

    Your browser can not display this movie.
    Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.

21. Create a test client TestRedBlackBST.java.