baryluk/bbtree — Issue #1: Change omega!
Author: baryluk
Created: 2011-10-31 06:32:41+00:00
State: open

omega >= 5 is wrong. It was first found by random testing, then by simple counterexample even for omega = 5, that it may produce not validly ballanced treed after delete_min (in Haskell's Data.Map, but not Data.Set which uses omega = 4). Change it to omega = 4, which looks to not create such problems, and actually makes set operations faster.

Look also to http://www.mew.org/~kazu/proj/weight-balanced-tree/ for a publication with formal proof of valid omega (integer) values.

Or use float value. (slower, and still can fail if float value is not approximate enough).