inserting and removing 500 things:
           Rate      fib   binary binomial   cheap2    cheap
fib      2.63/s       --     -17%     -35%     -76%     -98%
binary   3.15/s      20%       --     -22%     -71%     -97%
binomial 4.02/s      53%      28%       --     -63%     -96%
cheap2   10.8/s     311%     243%     169%       --     -90%
cheap     110/s    4065%    3374%    2623%     912%       --

1000 things:
           Rate      fib   binary binomial   cheap2    cheap
fib      1.24/s       --     -14%     -37%     -74%     -98%
binary   1.43/s      16%       --     -27%     -70%     -97%
binomial 1.97/s      59%      37%       --     -59%     -96%
cheap2   4.84/s     291%     238%     146%       --     -91%
cheap    54.8/s    4323%    3723%    2685%    1032%       --

2000:
           s/iter      fib   binary binomial   cheap2    cheap
fib          1.68       --      -9%     -39%     -73%     -98%
binary       1.54       9%       --     -33%     -70%     -98%
binomial     1.03      63%      49%       --     -56%     -96%
cheap2      0.456     269%     237%     126%       --     -92%
cheap    3.76e-02    4362%    3977%    2636%    1110%       --