1. Prove that the height of a red-black tree is at most 2 log N, and that this bound cannot be substantially lowered.
2. Show that every AVL tree can be colored as a red-black tree. Are all red-black trees AVL?
3. Draw a suf?x tree and show the suf?x array and LCP array for the following input strings:
a. ABCABCABC
b. MISSISSIPPI