A Random Binary Search Tree (commonly referred to as an RBST) is a binary search tree in which the ordering of the elements always remains random, regardless of the order of actual insertion. Tree's with randomly inserted elements have the nice property of being well balanced with a very high degree of probability.
For example:
Imagine inserting the elements 7 6 5 4 3 2 into a classic binary search tree (in that order). The resulting tree would
look like this:
7
/
6
/
5
/
4
/
3
/
2
That is a
horribly unbalanced tree (which is bad).
Now lets again insert the same elements into a classic binary search tree, but this time in a "random" order. Oh, say, 5 3 2 6 7 4. Here is what the tree would look like in this case:
5
/ \
3 6
/ \ \
2 4 7
This tree is much more balanced (and that's a
Good Thing).
Now if only there were a way to make the tree look as if its elements were inserted in random order, but regardless of the order in which the elements were actually inserted. Alas, there is a way! All you have to do is use a special insert operation. (The special insert operation is what makes it an RBST instead of a classic binary search tree.)
Here is the insert operation in pseudocode, and a description of how it works. Note that it is recursive, and calls 2 subroutines SIZE, and INSERT-AT-ROOT. Size is just the number of elements in the tree (that information should be kept in each node), and INSERT-AT-ROOT is also described below:
INSERT(tree T, item x)
with probability 1/(SIZE(T)+1)
INSERT-AT-ROOT(T, x);
else if(T->left > x)
INSERT(T->left, x);
else INSERT(T->right, x);
INSERT-AT-ROOT(tree T, item x)
tree L; //a "temp" tree to hold nodes smaller than x
tree R; //a "temp" tree to hold nodes greater than x
while T has children do
if(x > T AND T->right > x) //x is "between" T and T->right
remove subtree T->right as a child from T;
REGULAR-INSERT(L, T);
T = T->right;
else if(x > T->left AND T > x) //x is "between" T and T->left
remove subtree T->left as a child from T;
REGULAR-INSERT(R, T);
T = T->left;
else if(T->left > x)
T = T->left;
else //(x > T)
T = T->right;
REGULAR-INSERT(x,L); //make L the left child of x
REGULAR-INSERT(x,R); //make R the right child of x
return x;
The INSERT function works like this: With probability 1 in number of nodes in the tree (plus 1 for the new node to be inserted,) make the new node the root of the tree. otherwise recursively repeat the function on the left or right subtrees. (pick left or right depending on if the new element is greater or less than the current root of the tree.)
The INSERT-AT-ROOT function traverses the tree and "splits" the tree into peices that are either bigger or smaller than x. Those peices are combined into left and right subtrees, and then attached to the new node as its children.
The REGULAR-INSERT function is just the insert function from a normal binary search tree.
Using this INSERT algorithm will give us our desired behavior, that is, regardless of the order in which elements are inserted into the tree, it will always look like the elements were inserted in a "random" order, and therefore the tree will remain nicely balanced.
Lets say we have this RBST:
4
/ \
2 6
and we want to insert the element 5 into it. Here are all of the possible resulting trees:
(a) 5 (b) 4 (c) 4
/ \ / \ / \
4 6 2 5 2 6
/ \ /
2 6 5
Tree (a) is the result if 5 is inserted as the root of the entire tree. This will happen with probability 1/(3+1) = 1/4 = 0.25.
Tree (b) is the result if 5 is inserted as the root of the right subtree (the tree that has 6 as its root). This will happen with probability (1-(1/4))*(1/(1+1)) = 3/4 * 1/2 = 3/8 = 0.375.
Tree (c) is the result if 5 is inserted as the root of the left subtree of 6 (its a null tree, i.e., there are 0 elements in it). This will happen with probability (1-(1/4 + 3/8))*(1/(0+1)) = 1 - 5/8 * 1/1 = 3/8 * 1 = 3/8 = 0.375.
Note that the sum of the probabilities is 0.25 + 0.375 + 0.375 = 1.0, which is as it should be. (Otherwise 5 might never be inserted!)