11.48 util.rbtree - Red black tree

As of version 0.8.10, a balanced-tree object is built-in as <tree-map> (See section Treemaps), which uses red-black tree internally. It is recommended for applications to use <tree-map> instead of <rbtree>. This module is only kept for backward compatibility.

Module: util.rbtree

This module provides procedures to handle red black trees.

Red black tree is a kind of balanced binary tree. For a tree with n nodes, the basic operations such as searching, inserting, deleting, obtaining minimum and maximum element, and sequential access, can be done in O(log n). The keys used for red black trees must have total order.

API of util.rbtree is similar to the hash table API (See section Hashtables), so the user can use a red black tree as if it is a hashtable, with its entries are ordered by the keys.

Class: <rbtree>

A class for red black trees. Inherits <sequence>, so that you can apply sequence APIs on a red black tree. When treated as a sequence, each element is a pair of a key and a value.

Function: make-rbtree key=? key<?

Creates and returns an instance of <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.

Function: rbtree-copy rbtree

Copies and returns a red black tree rbtree. Modification on the returned tree doesn't affect the original tree.

Function: rbtree-empty? rbtree

Returns #t if rbtree doesn't have any elements, or #f otherwise.

Function: rbtree-num-entries rbtree

Returns the number of elements in rbtree.

Function: rbtree-exists? rbtree key

Returns #t if rbtree has an entry with key, or #f otherwise.

Function: rbtree-get rbtree key &optional fallback

Looks for key in rbtree. If the entry is found, returns a value corresponding to the key. Otherwise, returns fallback if it is provided, or signals an error.

Function: rbtree-put! 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.

Function: rbtree-delete! rbtree key

Delets an entry with key from rbtree if such an entry exists, and returns #t. If rbtree doesn't have such an entry, #f is returned.

Function: rbtree-update! rbtree key proc &optional fallback

A generalized version of rbtree-push! etc. It works like the following code, except that searching for the key is done only once.

(let ((tmp (proc (rbtree-get rbtree key fallback)))) (rbtree-put! rbtree key tmp) tmp)

Function: rbtree-push! rbtree key value

Looks for an entry with key in rbtree. If it exists, the procedure conses value to the original value and makes it as a new value. Otherwise, the procedure creates a new entry for the key and makes (list value) its value.

Function: rbtree-pop! rbtree key &optional fallback

Looks for an entry with key in rbtree. If it exists and its value is a pair, then the procedure updates its value with cdr of the original value, and returns car of the original entry. If such an entry does not exist, or has a non-pair value, the procedure doesn't modify rbtree and returns fallback if it is given, otherwise reports an error.

Function: rbtree-min rbtree &optional fallback

Function: rbtree-max rbtree &optional fallback

Returns a pair of a key and its value with the minimum or maximum key, respectively. If rbtree is empty, returns fallback if it is given, otherwise reports an error.

Function: rbtree-extract-min! rbtree &optional fallback

Function: rbtree-extract-max! rbtree &optional fallback

Looks for an entry with minimum or maximum key, respectively, then deletes the entry from rbtree and returns a pair of the key and its value of the original entry. If rbtree is empty, returns fallback if it is given, otherwise reports an error.

Function: rbtree-fold rbtree proc seed

Function: rbtree-fold-right rbtree proc seed

Iterate over elements in rbtree, applying proc which has a type (key, value, seed) -> seed. The difference of rbtree-fold and rbtree-fold-right is the same as fold and fold-right—that is, the associative order of applying proc.

rbtree-fold: (proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed))) rbtree-fold-right (proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))

Some examples:

(define tree (alist->rbtree '((3 . a) (7 . b) (5 . c)) = <)) (rbtree-fold tree list* '()) ⇒ (7 b 5 c 3 a) (rbtree-fold-right tree list* '()) ⇒ (3 a 5 c 7 b)

Function: rbtree-keys rbtree

Function: rbtree-values rbtree

Returns a list of all keys and all values, respectively. The keys and values are in ascending order of the keys.

Function: rbtree->alist rbtree

Returns a list of pairs of keys and values for all entries. The pairs are in ascending order of the keys.

Function: alist->rbtree alist key=? key<?

Creates a new red black tree with key=? and key<?, then populates it with alist, each pair in which are interpreted as a cons of a key and its value. Returns the created red black tree.

This document was generated by Shiro Kawai on October, 7 2008 using texi2html 1.78.