7
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Petr Pudlák May 3 '13 at 16:47
  • $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap May 3 '13 at 17:55
6
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.