You are looking at historical revision 20531 of this page. It may differ significantly from its current revision.

## rb-tree

A sorted dictionary data structure based on red-black trees.

## Usage

(require-extension rb-tree)

## Documentation

The `rb-tree` library is based on the SML/NJ library implementation of red-black trees, which is in turn based on Chris Okasaki's implementation of red-black trees. The delete function is based on the description in Cormen, Leiserson, and Rivest.

The present implementation code defines a red-black tree object that implements an ordered dictionary mapping of keys to values. The object responds to a variety of query and update messages, including methods for finding the minimum and maximum keys and their associated values as well as traversing the tree in an ascending or descending order of keys. Looking up an arbitrary or the min/max keys, and deleting the min/max keys require no more key comparisons than the depth of the tree, which is O(log n) where n is the total number of keys in the tree.

The rb-tree object is created by procedure `make-rb-tree`, the only user-visible procedure defined in this egg:

*[procedure]*

`make-rb-tree:: KEY-COMPARE-PROC [insert-key-compare: KEY-COMPARE-PROC] [delete-key-compare: KEY-COMPARE-PROC] -> SELECTOR`

where KEY-COMPARE-PROC is a user-supplied function that takes two keys and returns a negative, positive, or zero number depending on how the first key compares to the second.

Optional keyword arguments `insert-key-compare` and `delete-key-compare` can be used to specify different key comparison predicates for the insertion and deletion operations, respectively.

The returned selector procedure can take one of the following arguments:

`get`- returns a procedure
`LAMBDA KEY . DEFAULT-CLAUSE`which searches the red-black tree for an association with a given`KEY`, and returns a (key . value) pair of the found association. If an association with`KEY`cannot be located in the red-black tree, the PROC returns the result of evaluating the`DEFAULT-CLAUSE`. If the default clause is omitted, an error is signalled.`KEY`must be comparable to the keys in the red-black tree by a key-compare predicate (which has been specified when the red-black tree was created) `get-value`- returns a procedure
`LAMBDA KEY . DEFAULT-CLAUSE`which searches the red-black tree for an association with a given`KEY`, and returns the value of (key . value) pair of the found association. If an association with`KEY`cannot be located in the red-black tree, the PROC returns the result of evaluating the`DEFAULT-CLAUSE`. If the default clause is omitted, an error is signalled.`KEY`must be comparable to the keys in the red-black tree by a key-compare predicate (which has been specified when the red-black tree was created) `get-min`- returns a (key . value) pair for an association in the red-black tree with the smallest key. If the red-black tree is empty, an error is signalled.
`delete-min!`- removes the min key and the corresponding association from the red-black tree. Returns a (key . value) pair of the removed association. If the red-black tree is empty, an error is signalled.
`get-max`- returns a (key . value) pair for an association in the red-black tree with the largest key. If the red-black tree is empty, an error is signalled.
`delete-max!`- removes the max key and the corresponding association from the red-black tree. Returns a (key . value) pair of the removed association. If the red-black tree is empty, an error is signalled.
`empty?`- returns
`#t`if the red-black tree is empty `size`- returns the size (the number of associations) in the red-black tree
`depth`- returns the depth of the tree. It requires the complete traversal of the tree, so use sparingly
`clear!`- removes all associations from the red-black tree (thus making it empty)
`put!`- returns a procedure
`LAMBDA KEY VALUE`which, given a`KEY`and a`VALUE`, adds the corresponding association to the red-black tree. If an association with the same`KEY`already exists, its value is replaced with the`VALUE`(and the old (key . value) association is returned). Otherwise, the return value is`#f`. `put`- pure variant of
`PUT!`; it returns a new red-black tree object that contains the given association, while the original red-black tree object is unmodified. `delete!`- returns a procedure
`LAMBDA KEY . DEFAULT-CLAUSE`which searches the red-black tree for an association with a given`KEY`, deletes it, and returns a (key . value) pair of the found and deleted association. If an association with the KEY cannot be located in the red-black tree, the`PROC`returns the result of evaluating`DEFAULT-CLAUSE`. If the default clause is omitted, an error is signalled. `delete`- pure variant of
`DELETE!`; if the specified key is found, it returns a new red-black tree object that no longer contains the association specified by that key, while the original red-black tree object is unmodified. If the key is not found, the behavior of this procedure is identical to`DELETE!`. `for-each-ascending`- returns a procedure
`LAMBDA PROC`that will apply the given procedure PROC to each (key . value) association of the red-black tree, from the one with the smallest key all the way to the one with the max key, in an ascending order of keys. `for-each-descending`- returns a procedure
`LAMBDA PROC`that will apply the given procedure`PROC`to each (key . value) association of the red-black tree, in the descending order of keys. `map`- returns a procedure
`LAMBDA PROC`that will apply the given procedure`PROC`to the value component of each association in the red-black tree, in the ascending order of keys, and will construct a copy of the tree that contains the values returned by that procedure. `mapi`- returns a procedure
`LAMBDA PROC`that will apply the given procedure`PROC`to each (key . value) association in the red-black tree, in the ascending order of keys, and will construct a copy of the tree that contains the values returned by that procedure. `fold`- returns a procedure
`LAMBDA PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1)`the procedure returns the result of the successive function applications`(PROC value-1 (PROC value-2 ... (PROC value-n INITIAL)`. `foldi`- returns a procedure
`LAMBDA PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1)`the procedure returns the result of the successive function applications`(PROC key-1 value-1 (PROC key-2 value-2 ... (PROC key-n value-n INITIAL)`. `fold-right`- returns a procedure
`LAMBDA PROC INITIAL`such that, given the associations in the tree ordered by the ascending order of keys:`(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n)`the procedure returns the result of the successive function applications`(PROC value-n ... (PROC value-2 (PROC value-1 INITIAL)`. `foldi-right`- returns a procedure
`LAMBDA PROC INITIAL`such that, given the associations in the tree ordered by the ascending order of keys:`(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n)`the procedure returns the result of the successive function applications`(PROC key-n value-n ... (PROC key-2 value-2 (PROC key-1 value-1 INITIAL)`. `fold-partial`- returns a procedure
`LAMBDA PRED PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1)`the procedure returns the result of the successive function applications`(PROC value-i ... (PROC value-n INITIAL)`, where`i <= n`and`(PRED x)`holds true for all`x = (value-n) ... (value-i)`. In other words, this function acts like`fold`on the ordered subset of the values`x`in the tree such that`(PRED x)`is true. `foldi-partial`- returns a procedure
`LAMBDA PRED PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1)`the procedure returns the result of the successive function applications`(PROC key-i value-i ... (PROC key-n value-n INITIAL)`, where`i <= n`and`(PRED xk x)`holds true for all`x = (value-n) ... (value-i)`and`xk = (key-n) ... (key-i)`. In other words, this function acts like`foldi`on the ordered subset of the key-value pairs`(k . x)`in the tree such that`(PRED k x)`is true. `fold-right-partial`- returns a procedure
`LAMBDA PRED PROC INITIAL`such that, given the associations in the tree ordered by the ascending order of keys:`(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n)`the procedure returns the result of the successive function applications`(PROC value-1 ... (PROC value-i INITIAL)`, where`i <= n`and`(PRED x)`holds true for all`x = (value-1) ... (value-i)`. In other words, this function acts like`fold-right`on the ordered subset of the values`x`in the tree such that`(PRED x)`is true. `foldi-right-partial`- returns a procedure
`LAMBDA PRED PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-1 . value-1) (key-2 . value-2) ... (key-1 . value-1)`the procedure returns the result of the successive function applications`(PROC key-1 value-1 ... (PROC key-i value-i INITIAL)`, where`i <= n`and`(PRED xk x)`holds true for all`x = (value-1) ... (value-i)`and`xk = (key-1) ... (key-i)`. In other words, this function acts like`foldi-right`on the ordered subset of the key-value pairs`(k . x)`in the tree such that`(PRED k x)`is true. `fold-limit`- returns a procedure
`LAMBDA PRED PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1)`the procedure returns the result of the successive function applications`(PROC value-i ... (PROC value-n INITIAL)`, where`i <= n`and`(PRED x)`does not hold true for all`x = (PROC value-n INITIAL) ... (PROC (value-i) (PROC value-(i-1)...`. `fold-right-limit`- returns a procedure
`LAMBDA PRED PROC INITIAL`such that, given the associations in the tree ordered by the descending order of keys:`(key-1 . value-1) (key-2 . value-2) ... (key-i . value-1)`the procedure returns the result of the successive function applications`(PROC value-i ... (PROC value-1 INITIAL)`, where`i <= n`and`(PRED x)`does not hold true for all`x = (PROC value-1 INITIAL) ... (PROC (value-i) (PROC value-(i-1)...`.

## Examples

;; "--> Sorting of a set of numbers via a red-black tree" (define (++ x) (fx+ 1 x)) (define (-- x) (fx- x 1)) (let ((min-key -1) (max-key 10) (rb-tree (make-rb-tree (lambda (x y) (- x y)))) ;; a hard-wired association between a key and a value (compute-assoc (lambda (key) (cons key (++ key))))) ;; loading a sequence [min-key .. max-key] in ascending order (do ((i min-key (++ i))) ((> i max-key)) ((rb-tree 'put!) i (cdr (compute-assoc i)))) (print "the tree depth is " (rb-tree 'depth) "\n") (print ((rb-tree 'get) (++ min-key))) (print ((rb-tree 'get) (++ min-key) 'notfound)) ;; checking traversing in ascending order (let ((expected-key min-key)) ((rb-tree 'for-each-ascending) (lambda (association) (print (equal? association (compute-assoc expected-key))) (set! expected-key (++ expected-key))))) ;; clearing the rb-tree and reloading the same sequence in ;; descending order (rb-tree 'clear!) (do ((i max-key (-- i))) ((< i min-key)) ((rb-tree 'put!) i (cdr (compute-assoc i)))) (print "the tree depth is " (rb-tree 'depth) "\n") ;; checking traversing in descending order (let ((expected-key max-key)) ((rb-tree 'for-each-descending) (lambda (association) (print (equal? association (compute-assoc expected-key))) (set! expected-key (-- expected-key))))))

## About this egg

### Author

### Version history

- 3.1
- Added get-value operation
- 3.0
- Ability to specify different predicates for lookup, insert, delete operations
- 2.9
- Documentation converted to wiki format
- 2.8
- Added matchable as dependency
- 2.7
- Bug fix in dispatch-on-key
- 2.6
- Ported to Chicken 4
- 2.5
- Fixes to for-each-ascending/descending
- 2.3
- Build script updated for better cross-platform compatibility
- 2.2
- Added fold-limit procedures
- 2.1
- Added fold-partial procedures
- 2.0
- Added side-effect-free put and delete procedures
- 1.0
- Initial release

### License

Copyright 2007-2010 Ivan Raikov and the Okinawa Institute of Science and Technology. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>.