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.
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
weightin the code is used differently than the alpha in the wiki article, or whether it is a bad idea to setweightto4.