11.49 util.rbtree - 赤黒木

バージョン0.8.10から、バランス木オブジェクトは<tree-map>として 組込みになっています (ツリーマップ参照)。内部的には赤黒木が使われています。 アプリケーションは<rbtree>ではなく<tree-map>を使うことが 推奨されます。このモジュールは互換性のために残されています。

Module: util.rbtree

このモジュールは、赤黒木 (red-black tree、2色木)を扱う手続きを提供します。

赤黒木は平衡な(バランスの取れた) 2分木の一種です。nノードからなる木 に対する基本的な操作(要素の探索、挿入、削除、最初および最大の要素の 取得、要素の順次アクセス)は、O(log n)で行われます。赤黒木に追加する 要素のキーは、要素間に全順序関係が定義されていなければなりません。

util.rbtreeのAPIはハッシュテーブルのAPIに似せて作られており、ユーザ は赤黒木を、キーの大小で順序付けられたハッシュテーブルのように扱う ことができます (ハッシュテーブル参照)。

Class: <rbtree>

赤黒木のクラスです。<sequence>を継承しているので、 gauche.sequenceで定義されるAPIを使うことができます。 シーケンスとして扱うときの各要素は、キーと値のペアです。

Function: make-rbtree key=? key<?

<rbtree>オブジェクトを作成して返します。key=?、key<?はそれぞれ引 数を2つ受け取り真偽値を返す手続きであり、要素のキーが渡されます。 key=?は、2つの引数a, b が同値の場合に真を、それ以外の場合に#fを 返す手続きです。key<?は、a < bが成り立つ場合に真を、それ以外の 場合に#fを返す手続きです。

Function: rbtree-copy rbtree

赤黒木rbtreeのコピーを作り、それを返します。返された赤黒木に対す る破壊的操作は、元の赤黒木に影響を与えません。

Function: rbtree-empty? rbtree

赤黒木rbtreeが要素を持たないなら#tを、そうでなければ#fを 返します。

Function: rbtree-num-entries rbtree

赤黒木rbtree内の要素の個数を返します。

Function: rbtree-exists? rbtree key

赤黒木rbtreeにキーkeyを持つエントリがあれば#tを、 そうでなければ#fを返します。

Function: rbtree-get rbtree key &optional fallback

キーkeyを赤黒木rbtreeから探します。見つかればkeyに対応する値を返 します。キーが見つからなかった場合、fallbackが与えられていればそれ を返し、そうでなければエラーを報告します。

Function: rbtree-put! rbtree key value

キーkeyと対応する値valueを赤黒木rbtreeに挿入します。もし、keyと、 key=?における意味で同じキーがすでに存在する場合、キーに対応する値 は新たな値に置き換えられます。

Function: rbtree-delete! rbtree key

赤黒木rbtreeからキーkeyを持つエントリを削除します。keyを持つエン トリが実際に存在して削除された場合は#tを、エントリが存在しなかっ た場合は#fを返します。

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

rbtree-push!等のより一般的なバージョンです。赤黒木の探索が一度 しか行われないことを除いては、基本的に次のように動作します。

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

Function: rbtree-push! rbtree key value

赤黒木rbtree中の、キーkeyに対応する値にvalueをコンスし、それをkey に対する新たな値とします。もしkeyに対応する値がまだ無ければ、新た なエントリが作成され、(list value)がその値となります。

Function: rbtree-pop! rbtree key &optional fallback

赤黒木rbtree中のキーkeyに対応する値が存在し、かつペアであった場合 に、そのエントリの値を元の値のcdrで置き換え、元の値のcarを返します。 keyに対応する値が存在しないかペアではなかった場合、赤黒木rbtreeは 変更されず、fallbackが与えられていればそれが返され、与えられていな ければエラーが報告されます。

Function: rbtree-min rbtree &optional fallback

Function: rbtree-max rbtree &optional fallback

それぞれ、赤黒木rbtreeに含まれる最小および最大のキーを探索し、その キーと値のペアを返します。赤黒木rbtreeが空だった場合は、fallbackが 指定されていればそれを返し、そうでなければエラーを報告します。

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

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

それぞれ、赤黒木rbtreeに含まれる最小および最大のキーを探索し、そ のエントリを赤黒木rbtreeから削除したうえで、そのキーと値のペアを 返します。赤黒木rbtreeが空だった場合は、fallbackが指定されていれば それを返し、そうでなければエラーを報告します。

Function: rbtree-fold rbtree proc seed

Function: rbtree-fold-right rbtree proc seed

rbtreeの各要素に対し、(key, value, seed) -> seed の型を持つ procを適用してゆきます。 rbtree-foldとrbtree-fold-rightの違いは foldのfold-right違いと同じ、すなわち 結合の方向にあります。

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)))

例:

(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

それぞれ、赤黒木rbtree内の全てのキーまたは値をリストにして返しま す。返されるリストの要素はキーの昇順に並んでいます。

Function: rbtree->alist rbtree

赤黒木rbtree含まれる要素を連想リストにして返します。返される連 想リストのキーは昇順に並んでいます。

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

key=?, key<? によって新たな赤黒木を作成し、 連想リストalistに含まれる要素を追加し、その木を返します。

This document was generated by Shiro Kawai on November, 22 2009 using texi2html 1.78.