This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 60

Simpler Randomized BST, Part 2

Due: March 8
Points: 2

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:

  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.