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 >= 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 dept

Your proof/argument is not valid.

First, I see a claim about the probability that the adversary can trigger a rotation, but no proof of this claim. Every claim should be justified. Also, the claim is not precisely defined; it is not entirely clear how "a rotation that impairs balance" should be interpreted.

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.

StackExchange Computer Science Q#35418, answer score: 3