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.

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`