ruby picture

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
ruby picture
Comments Current voting
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
ruby picture
If you have registered at RCRchive, you may now sign in below. If you have not registered, you may sign up for a username and password. Registering enables you to submit new RCRs, and vote and leave comments on existing RCRs.
Your username:
Your password:

ruby picture

Powered by .