Problem 50

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Simpler Randomized BST, Part 2

Due: March 1
Points: 4

Check out the "simpler" randomized BST insertion algorithm described in problem 49. As it turns out, this is "too simple" - meaning that it doesn't actually work! Answer two questions for me:

1. 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?
2. 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.