単純な2分探索木の弱点

1.upto(1000) do |i|
	hash[i] = i
end
1000.downto(1) do |i|
	hash.delete( i )
end

こんなテストだと単純な2分探索木では激重になる。

                user     system      total        real
Hash        0.000000   0.000000   0.000000 (  0.000000)
MyHash1     2.593000   0.000000   2.593000 (  2.594000)
MyHash2    12.563000   0.734000  13.297000 ( 13.297000)
MyHash2M    6.016000   0.000000   6.016000 (  6.031000)
MyHash3     0.093000   0.000000   0.093000 (  0.094000)
MyHash4     0.203000   0.000000   0.203000 (  0.203000)

MyHash2とMyHash2Mが単純な2分探索木による連想配列の実装。
MyHash1の単純な線形探索にも負けている。