# Proof of Randomized Self-Adjusting Binary Search Tree

I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). I've since given up the hope of publishing (I'm not an academic so it doesn't matter so much), but perhaps I can have some closure: I'm going to present the tree here, and perhaps someone can help me understand where my proofs fall short? Through testing, I'm quite certain that my understanding of the data structure is correct, but the proofs were always lacking.

First, understand how a top-down splay tree can be implemented around a traverse() function. Shuffle trees can be implemented similarly, where all operations defer to a traverse() function for the balancing operation.

I'm going to begin with a C traverse function for shuffle trees, then I'll explain:

// returns node with key k,
// or returns the leaf containing
// the closest key to k.
node *  Traverse( key k, node *root, int treesize ) {
signed int iCounter = rand() % treesize;
node *pRet = 0;
node *p = root;
while ( p ) {
pRet = p;
if ( k < value(p) ) {
p = left(p);
if (( ! iCounter )&& p ) {
RotateRight( pRet );
pRet = parent(p);
} // end if
} else if ( value(p) < k ) {
p = right(p);
if (( ! iCounter )&& p ) {
RotateLeft( pRet );
pRet = parent(p);
} // end if
} else
break ; // break while
--iCounter;
iCounter >>= 1;
} // end while
return ( pRet );
}


The rotations used are simple single rotations.

Like a scapegoat tree, shuffle trees sample depth to find imbalance, but unlike scapegoat trees, they execute at most one rotation per access to attempt to restore balance.

At the beginning of traversal, we set an integer count-down value, to a random number in the range [0,N-1], where N is the size of the tree. As we iterate from a parent node to its child, we decrease the counter with I := (I-1)/2. When the counter equals zero, then the current node becomes a candidate rotation pivot. If we need to iterate past the candidate pivot, then we will commit to the rotation. We rotate the pivot away from the direction of traversal.

As search depth increases, the likelihood of a rotation increases. No rotations will occur beyond depth lgN. The counter requires lgN random bits per operation. Shuffle trees also record their size, so that the counter can be set. No balancing information needs to be recorded in tree nodes. Searches may not navigate to a leaf; if the working set is clustered near the root, then deep searches will not be required. As a result, rotations can occur less frequently in a well-configured tree. If a node in the tree is not weight-balanced, then an access is more likely to traverse into its larger sub-tree. A rotation at the node probably moves some of the descendants from the larger sub-tree to the smaller one. Since these operations are probabilistic, rotations will occur which can deteriorate balance; but as the imbalance increases, the likelihood of a rotation that improves balance increases. In effect, the balancing technique is a kind of random sampling. Nodes are selected randomly from traversal paths and their balance is manipulated. Frequently used data attract more attention and, therefore, benefit more from balancing activity than infrequently used data. The tree eventually approximates a weight-blanced configura tion for the data set, where the probability of access is the weight for each node.

Here's where it gets dicey: proving that a traversal occurs in lgN.

I argue the probability that an adversary can select a node to force a rotation that impairs balance is

(1 - Pw) * Product over A of ( 1 - px )


Where Pw is a number estimating the overall weight balance of the tree (Pw >= 0.5) and px is the weight of node x, the probability it is accessed. Set A is the set containing the pivot and all its ancestors.

If rotations occur which impair balance, and Pw increases, then the overall probability of a favorable rotation increases. As Pw increases, the probability of a favorable rotation dwarfs the probability of a poor rotation. The tree does not linearize, and lgN is maintained.

Eh. What do you think?

• Can you articulate a more specific question than "What do you think?" You say you want feedback on your proofs. This site format probably isn't a good format for reviewing complex material like this or checking proofs. Also, I don't see any proof here. Can you give a more precise statement of the claim you want to prove? What do you mean by "probability"? Probability over what space? What random variables? I don't see any randomness in your algorithm. Lastly, can you replace the C code with concise pseudocode, for people here who don't read C? – D.W. Mar 20 '17 at 17:48
• I don't entirely grasp your probabilistic argument (I don't see how the probabilities are defined, for one), but I spotted 2 potential problems: 1. You argue that bad rotations are unlikely and therefore unlikely to lead to problems. However, unlikely situations will occur eventually. Therefore, you at least have to show that the expected number of times a bad rotations occurs combined with the expected 'damage' it does has a certain asympotic bound. 2. If something is not linear, it does not means it is logarithmic. It could very well be $O(\sqrt{n})$ or something else entirely. – Discrete lizard Mar 20 '17 at 17:56

Second, a statement like "The tree does not linearize, and lgN is maintained" has no place in a proof. In a proof, you must justify all statements: every statement must follow logically from things you've previously demonstrated. That statement comes out of nowhere and doesn't follow. For instance, as @Discrete lizard explains, just because a tree's height is less than $n$ doesn't necessarily imply the height is $O(\lg n)$; there are many other possibilities for what its height could be.
• @MayurPatel, OK, sorry, I missed the call to rand(). I've revised my answer accordingly. – D.W. Mar 27 '17 at 16:13