[Solved]: Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?

Problem Detail: 

This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$

Definition: For a rooted tree $T$ and a vertex $v \in V(T)$, let $L_T(v)$ be the number of nodes in the left-subtree from $v$, and $N_T(v)$ be the number of nodes in the subtree rooted at $v$. We say that $T$ is $\mu$-balanced, with $0 \le \mu \le \frac{1}{2}$, if for every node $v \in V(T)$ the inequality $$ \mu \le \frac{L_T(v) + 1}{N_T(v) + 1} \le 1 - \mu$$ holds, and if $\mu$ is minimal subject to this inequality holding.

(These are apparently also known as weight-balanced trees in some of the literature.) A tree which is $\mu'$-balanced for some $\mu' < \mu$, we will say is μ-imbalanced.

The above-linked posts essentially show that neither AVL trees, nor Red-Black trees, can be guaranteed to be $\mu$-balanced for any $\mu > 0$: that is, for any such $\mu$, one can provide a sequence of inputs to be inserted so that the resulting tree is $\mu$-imbalanced.

Question. Is there any binary search tree structure, with the usual characteristics of $O(\log n)$ insertion and search time, and some $m > 0$, such that the tree will always be $\mu$-balanced for some $\mu > m$?

Asked By : Niel de Beaudrap

Answered By : Aryabhata

Yes, I believe there is (though I don't remember the details of the paper to confirm).

This is the original paper which dealt with that:

Nievergelt J. and Reingold E.M., "Binary search trees of bounded balance", Proceedings of the fourth annual ACM symposium on Theory of computing, pp 137--142, 1972

Here is a page on weight-balanced trees which seems to have some more information and mentions their usage in functional languages.

This paper: On Average number of rebalanced operations in weight balanced trees, seems to be investigating the number of rebalancing operations in weight balanced trees.

I also seem to remember that one Knuth's Art of ... books had a reference to the above Reingold paper (perhaps in the exercises).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11756