RCRchive		Top	Help	RSS	Contact	Credits

This is the old RCRchive. It's available only for reading and reference. To submit RCRs for Ruby 1.9/2.0, and to participate in discussions about them, please visit the new RCRchive.

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 http://raa.ruby-lang.org/project/ruby-rbtree/

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	10
Strongly advocate	17