Gauche:RedBlackTree
(Rui): Red-black treeを実装しました。いくつかアドバイスをいただきたい点があります。
- gauche.collectionがfold-rightを提供していないので、自前で用意しましたが、fold-rightがあるといいですね。red-black treeでは右から左へのアクセスも左から右へのアクセスも同じコストなので、各要素に対してconsして最後にreverse!する代わりにfold-rightを使ったほうが速いので。
- call-with-builderに渡されるキーワード引数を、map-toなどから渡す方法はないですか?
- こういうモジュールの分類ってdataが適切なんでしょうか? → utilにしました。
ソースはこちらから。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のジェネリック手続きを使えばよいと考えたからですが、とくにそれでいいですよね?