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.