From: Bill Kelly <billk@...>
Date: 2010-03-22T10:59:17+09:00
Subject: [ruby-core:28851] Re: [Feature #2348] RBTree Should be Added to the Standard Library

Hi,

Yusuke ENDOH wrote:
> 
> Is there case where we want to use RBTree directly, instead of set.rb?

I'm sorry if I've misunderstood - but it would not have occurred
to me to use 'set' to access RBTree's functionality.

RBTree and MultiRBTree (both provided by require 'rbtree') are
akin to std::map and std::multimap in C++ STL.

It has long been a mystery to me that a Sorted Pair Associative
Container with O(log N) insert, search, and delete complexity
has not been a part of ruby's stdlib.

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.)

RBTree and MultiRBTree are very useful container types when
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.

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?


Regards,

Bill