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