0
$\begingroup$

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

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

1 Answer 1

Reset to default
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented Feb 9, 2019 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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