# 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' < \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$?

• I'd say that the reason why $\mu$-balanced trees are rarely used: they require too much overhead when balancing them, with a little gain. Consider the example in this answer: The tree has height $2k+2$. It's left subtree has $2^k-1$ nodes and its right subtree has $2^{2k+1}-1$ nodes, so overall it has $2^{2k+1}+2^k-1$. If we put the same number of nodes into a perfectly balanced tree, it will still have height $2k+2$. Since the height is what determines operation costs, we gain nothing, we only spend much more time re-balancing.
– Petr
May 3 '13 at 16:47
• @PetrPudlák: Indeed, reading Binary search trees of bounded balance (Nievergelt+Reingold) in Aryabhata's answer, I'm struck by the oddness of the idea of searching by traversing the entire data structure. I'm not sure under what circumstances one might want to do such a thing, which wouldn't suggest either a simpler or a more elaborate data structure instead. If finding the path to the sought-for element is easy, as in a typical implementation of BSTs on an ordered set, it's height but not weight which matters; but as a combinatoricist I'm curious. May 3 '13 at 17:55