Fix tests for Data.Set; use balanced invariant instead of log_size (which was always True)
Closes #96 (closed).
The Haskell version has
delta = 3, and this is also what Data.Map uses.
Note that there is some discussion on correct settings of
ratio in the comments immediately above:
// Note that according to the Adam's paper: // - [delta] should be larger than 4.646 with a [ratio] of 2. // - [delta] should be larger than 3.745 with a [ratio] of 1.534. // // But the Adam's paper is erroneous: // - It can be proved that for delta=2 and delta>=5 there does // not exist any ratio that would work. // - Delta=4.5 and ratio=2 does not work. // // That leaves two reasonable variants, delta=3 and delta=4, // both with ratio=2. // // - A lower [delta] leads to a more 'perfectly` balanced tree. // - A higher [delta] performs less rebalancing. // // In the benchmarks, delta=3 is faster on put operations, // and delta=4 has slightly better deletes. As the put speedup // is larger, we currently use delta=3.
This is identical to the comment Haskell version, but it is not clear to me what the author means to say with the two points below "But the Adam's paper is erroneous". In any case, it seems to me that it is not proven at all that