RCR 306: include rbtree in the stdlib
Submitted by martindemello (Sat May 14 15:51:24 UTC 2005)
A good red/black tree implementation in the standard library would enable several algorithms to be implemented more efficiently.
There is, as yet, no efficient implementation of data structures such as a priority queue and a sorted collection in ruby's standard library. This often leads to algorithmically suboptimal but implementationally convenient reinventions of the wheel.
Add a red/black tree implemetation to the standard library, and classes like a Priority Queue and Sorted List as interfaces to it.
While there's a red/black tree available in the RAA, a balanced tree is a fundamental enough data structure that one should be available by default.
There's already one at
I would love to see this happen, especially an optimal C version. --Ari
It's been years since I voted one way or another on *any* RCR, but I just gotta vote for this one. /vjoel/
RCRchive copyright © David Alan Black, 2003-2005.
Powered by .