[ruby-core:28853] Re: [Feature #2348] RBTree Should be Added to the Standard Library

Hi,

2010/3/22 Bill Kelly <[e-mail]>:
> RBTree and MultiRBTree provide functionality which, with its
> worst-case O(log N) search, insert, and delete complexity for
> a sorted pair associative container can't be readily duplicated
> with Array, Hash, or Set. ?(As far as I know.)

Hash has amortized O(1) search, insert, and delete complexity,
I think.  Indeed, it becomes O(N) at worst-case (when rehash
occurs).  Does anyone have a concrete problem due to rehash?

I think this feature request is very tough because it can be
substituted by Hash in many cases.  So I think you guys should
appeal the difference.  It would be good to show some real-world
case where Hash cannot be used and RBTree is really needed.


> I do think the "RB" portion of the name is slightly unfortunate,
> as we don't generally care that it is implemented as a red-black
> tree internally; we just care about O(log N) complexity
> guarantees.

True.


> Anyway - I apologize if i've merely regurgitated a litany of
> obvious points into the conversation. ?I didn't really
> understand why RBTree/MultiRBTree would be considered a
> variant of Set?

There is no use case presented other than set, as far as I read.

-- 
Yusuke ENDOH <[e-mail]>