# Is there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1?

I am wondering if there is a log time WBT (weight balanced binary search tree) data structure in which for any node, the sizes of its left and right subtrees diff at most by 1.

PS: I have read through Balancing weight-balanced trees but the weights of subtrees can differ up to a factor of $\Delta$.

• Your title isn't a very good advertisement for your question. – Yuval Filmus Dec 23 '16 at 12:37
• @YuvalFilmus I've edited the title but it's more verbose as well now. Please feel free to improve it. – wlnirvana Dec 24 '16 at 9:52

## 1 Answer

Refer the following paper; https://www.researchgate.net/publication/2241064_A_New_Weight_Balanced_Binary_Search_Tree. It has both bottom-up and top-down restructuring.

• I don't see how this answers the question. On a quick glance, it looks like that paper concerns itself with the ratio of sizes of left and right subtrees, but doesn't try to argue whether one can ensure the size of left and right differ by at most one. If I'm missing something, can you edit your question to clarify the relevance of that paper and to summarize its key results, as they apply to this question? – D.W. Feb 9 '19 at 19:48