On Jun 3, 2006, at 9:49 PM, Victor Shepelev wrote:

> From: transfire / gmail.com [mailto:transfire / gmail.com]
> Sent: Sunday, June 04, 2006 4:43 AM
>> Please example more. Do you mean:
>>
>>  [ 2, 1, 3, 0 ].sort  #=> [ 0, 1, 2, 3 ]
>
> Nope. I've meant:
>
> lst = SortedList.new(3, 1, 4, 0)
>
> lst.to_a #=> [ 0, 1, 3, 4 ]
>
> lst.insert(2)
> lst.to_a #=> [ 0, 1, 2, 3, 4 ]
>
>> T.
>
> V.
>
>

I was going to suggest http://raa.ruby-lang.org/project/ruby-rbtree/
but it is written in C.

However, this is as far as I can tell pure ruby:
http://raa.ruby-lang.org/project/ruby-treap/