Problem
1. Show that the nodes of any AVL tree T can be colored "red" and "black" so that T becomes a red-black tree.
2. Consider a variation of splay trees, called half-splay trees, where splaying a node at depth d stops as soon as the node reaches depth [d/2\. Perform an amortized analysis of half-splay trees.