Is there a binary search tree datastructure which can avoid becoming badly weight-balanced? 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' &lt; \mu$, we will say is &mu;-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 &gt; 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 &gt; 0$, such that the tree will always be $\mu$-balanced for some $\mu &gt; m$?
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).