You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Hi! I just took a superficial look at the bbtrees implementation, because I was looking for the simple binary trees implementation and thought maybe that bb stands for "balanced binary". Anyway, I ended up reading about "trees of bounded balance" a.k.a. "weight balanced trees" on Wikipedia. There is states, that the balancing factor alpha should be much lower than 4:
[…] but not all values of α are appropriate; Nievergelt and Reingold proved that [… formula as picture …] is a necessary condition for the balancing algorithm to work. Later work showed a lower bound of 2⁄11 for α […] -- https://en.wikipedia.org/wiki/Weight-balanced_tree
So I wonder, if that weight in the code is used differently than the alpha in the wiki article, or whether it is a bad idea to set weight to 4.
The text was updated successfully, but these errors were encountered:
Hi! I just took a superficial look at the bbtrees implementation, because I was looking for the simple binary trees implementation and thought maybe that bb stands for "balanced binary". Anyway, I ended up reading about "trees of bounded balance" a.k.a. "weight balanced trees" on Wikipedia. There is states, that the balancing factor alpha should be much lower than 4:
So I wonder, if that
weight
in the code is used differently than the alpha in the wiki article, or whether it is a bad idea to setweight
to4
.The text was updated successfully, but these errors were encountered: