Gauche:RedBlackTree

Gauche:RedBlackTree

(Rui): Red-black treeを実装しました。いくつかアドバイスをいただきたい点があります。

ソースはこちらから。rbtree.scm.txt, rbtree-test.scm.txt


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

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

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

クラス: <rbtree>

赤黒木のクラスです。`<collection>'を継承しているので、 `gauche.collection'を使うことができます。コレクションとして扱うと きの各要素は、キーと値のペアです。

手続き: make-rbtree key=? key<?

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

手続き: rbtree-get rbtree key &optional default

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

手続き: rbtree-put! rbtree key value

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

手続き: rbtree-delete! rbtree key

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

手続き: rbtree-exists? rbtree key

赤黒木RBTREEにキーKEYを持つエントリがあれば`#t'を返します。

手続き: rbtree-push! rbtree key value

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

手続き: rbtree-pop! rbtree key &optional default

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

手続き: rbtree-update! rbtree key proc &optional default

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

     (let ((tmp (proc (rbtree-get RBTREE KEY DEFAULT))))
       (rbtree-put! RBTREE KEY tmp)
       tmp)

手続き: rbtree-empty? rbtree

赤黒木RBTREEが要素を持たないなら、真を返します。

手続き: rbtree-min rbtree &optional default

手続き: rbtree-max rbtree &optional default

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

手続き: rbtree-extract-min! rbtree &optional default

手続き: rbtree-extract-max! rbtree &optional default

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

手続き: rbtree-copy rbtree

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

手続き: rbtree-num-entries rbtree

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

手続き: rbtree-keys rbtree

手続き: rbtree-values rbtree

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

手続き: rbtree->alist rbtree

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

手続き: alist->rbtree alist

連想リストALISTに含まれる要素を赤黒木に追加し、その木を返します。


議論、コメント

Shiro: おお、すばらしい。もし良ければGauche本体に取り込ませて 頂けませんか (テストがあるとなお素晴らしいです)。 モジュール名については、util.rbtreeでどうでしょう。data.* というのは 昔考えていたのですが、こういうアルゴリズムの実装に対して使うのはちょっと どうかなという気がしてきているので。

fold-rightについてはgauche.collectionにあると便利ですね。追加します。

call-with-builderに渡すキーワード引数か…これはアイディアが無いです。 まりトリッキーな仕様にしたくは無いですが、何かいいアイディアありませんか?

Rui: もちろん喜んで。テストは置いておきます。モジュールの名前はutil.rbtreeに変更しました。いまいちなところはよしなに変更してください。

call-with-builderについては特にアイデアはありません。あんまりよく考えていないというか、実際、map-toなどでrbtreeを作りたい状況というのがないような気がするので。

そうそう、hash-table-foldやhash-table-for-eachに相当する手続きは用意しませんでした。これは、gauche.collectionのジェネリック手続きを使えばよいと考えたからですが、とくにそれでいいですよね?

More ...