単純な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の単純な線形探索にも負けている。