Problem 49

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 1

Due: March 1
Points: 3

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`