scheme-rbtrees's Introduction

What is this?

Red-black tree (http://en.wikipedia.org/wiki/Red-black_tree) implmentation for R6RS. The implementation is based on "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Using Red-black tree

Put rbtree.ss to your LOADPATH.

(import (rnrs) (rbtree))
(let ([rb (make-rbtree string=? string<?)])
  (rbtree-get rb "abc" 'not-found) ;; => 'not-found
  (rbtree-set! rb "abc" 'val1)
  (rbtree-get rb "abc") ;; => 'val1
  (rbtree-delete! rb "abc")
  (rbtree-get rb "abc" 'not-found)) ;; => 'not-found

API

(make-rbtree key=? key<?)
- Creates and returns an rbtree. The arguments key=? and key<? are both procedures that take two arguments, which are the keys. The key=? procedure should return #t if two arguments are equivalent, or #f otherwise. The key<? procedure should return #t if the first argument is strictly less than the second argument, or #f otherwise.
(rbtree? obj)
- Returns #t if obj is rbtree, otherwise #f.
(rbtree-set! rbtree key value)
- Inserts an entry with a key and corresponding value into rbtree. If there already exists an entry with a key which is equivalent (under key=?), the entry is modified to have value.
(rbtree-delete! rbtree key)
- Deletes an entry with key from rbtree if such an entry exists, and returns #t otherwise #f.
(rbtree-get rbtree key . fallback)
- Returns value associated with key. If key is not found and fallback is specified, returns fallback, otherwise raise error.
(rbtree-size rbtree)
- Returns number of elementes.
(rbtree-contains? rbtree key)
- Returns #t if rbtree has value associated with key, otherwise #f.
(rbtree-keys rb)
- Returns keys in ascending order of the keys.