RCR 306: include rbtree in the stdlib
Submitted by martindemello (Sat May 14 15:51:24 UTC 2005)
Abstract
A good red/black tree implementation in the standard library would enable several algorithms to be implemented more efficiently.
Problem
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.
Proposal
Add a red/black tree implemetation to the standard library, and classes like a Priority Queue and Sorted List as interfaces to it.
Analysis
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.
Implementation
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/
|
Strongly opposed |
0 |
Opposed |
0 |
Neutral |
0 |
In favor |
9 |
Strongly advocate |
16 |
|
RCRchive copyright © David Alan Black, 2003-2005.
Powered by .
It's been years since I voted one way or another on *any* RCR, but I just gotta vote for this one. /vjoel/