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 59

Simpler randomized BST, Part 1

Due: March 8
Points: 2

Here is a simpler algorithm for a randomized binary search tree: do each insertion like in a normal binary search tree, so that the new node is a new leaf in the tree. Then do a "randomized bubble-up" algorithm that randomly rotates the new leaf up one level, depending on whether a randomly-chosen bit is 0 or 1. So it works kind of like skip-list insertion where everything is inserted on the bottom level, and then randomly raised up by flipping a coin (choosing random bits) until we get a 1.

For example, say we have the following tree to start out with:

        10
      /    \
     7      15
    / \    /
   2   8  12   

And we want to insert a new node with key 5, so we start by inserting it at the leaf position like in any BST:

        10
      /    \
     7      15
    / \    /
   2   8  12   
    \
     5

And then we randomly choose bits 0 or 1, and rotate the 5 up the tree until we choose a 1 or until 5 hits the root. So for example, if the first random bit is a 1, the resulting tree will be just like you see it above. If the random bits are 0,0,1, then 5 will get rotated up twice, like so:

       10
     /    \
    5      15
   / \     /
  2   7   12
       \
        8

Show what the resulting tree is, if we start with an empty tree and insert the following keys:

[94, 79, 84, 54, 88, 23, 54]

and if the random bits are the following:

1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0