RAA - ruby-treap

ruby-treap / 0.2.0

Short description: A probabilistically balanced binary search tree

Category: Library/Datastructure

Status: beta

Created: 2006-03-05 18:08:39 GMT

Last update: 2006-03-05 18:08:39 GMT

Owner: andrew (Projects of this owner)

Homepage: http://stuff.siaris.net/index.cgi/code/

Download: http://stuff.siaris.net/code/ruby/Treap.tar.gz

License: Ruby's

Dependency:

None

Description:

Treap

Treap — tree + heap == treap

A randomized binary tree using random priorities in heap order to maintain a probabilistically balanced tree. See, for example:

  http://en.wikipedia.org/wiki/Treap

Synopsis

  require 'treap'
  tree = Treap.new
  i = 0
  %w- f w a q b c l r d -.each {|k| tree.insert(k, i += 1)}
  tree.each_pair {|k,v| print "<#{k}:#{v}>"}
  print "\n"
  __END__

  <a:3><b:5><c:6><d:9><f:1><l:7><q:4><r:8><w:2>

  # also supports a hash-like interface, providing for
  # ascending/descending key-ordered hashes

Requirements:

Ruby 1.8+

Install

  ruby setup.rb config
  ruby setup.rb install

  ruby setup.rb --help  # for installation help

darcs

You can grab it from my darcs repository as well:

  darcs get http://repos.siaris.net/ruby/Treap

Edit this project (for project owner)

back to RAA top