Simpler Randomized BST, Part 2Due: March 8
Check out the "simpler" randomized BST insertion algorithm described in problem 59. As it turns out, this is "too simple" - meaning that it doesn't actually work! Answer two questions for me:
- What would be the advantage to this "simpler" BST, compared to the regular randomized BST that we talked about, if we could show that the expected height was still \(\Theta(\log n)\) after \(n\) insertions?
- The expected height is actually not \(\Theta(\log n)\). You don't have to prove this, but explain why this might be the case. Describe a series of unlucky choices that leads to an unbalanced tree, and then say why the tree is likely to stay unbalanced in future insertions.