sile / veb-tree Goto Github PK

============
=== 概要 ===
・common lispによるVan Emde Boas Tree(vEB-tree)の実装
・Van Emde Boas Tree
　・多分木
　・要素の挿入/検索/削除がO(log log M)で行える
　　・要素は正の整数値に限定
　　　=> 本来は整数値のキーと値を紐付けたマップ(or 連想配列)的な使い方をするのだろうが
　　　　 今回の実装では未対応
　　・Mは要素の最大値
　・優先順序付きキューとして利用可能
　　・「次に小さい要素」の検索もO(log log M)で行える

※ 以降はメモ
　・メリット
　　・平衡二分木よりも処理オーダーが良い
　　・要素セットが大きい場合はサイズ効率も良い
　　　=> 二分木よりもポインタ(参照)のために必要な領域が少なくなるため

　・デメリット
　　・要素セットが小さい場合(or 要素セットが疎な場合)には、オーバヘッドが大きい
　　・要素の最大値をあらかじめ指定しておく必要がある

　・実装
　　・(配列を用いた)トライ木と似ており、各ノードの探索時に先頭からxビットずつを使って、対象となる子ノードを検出する
　　・ただし、トライ木は全てのノードで一律に同じサイズのxビットを使うのに対して、
　　　vEB木は、最初のノードでは、キーのビット長さの半分を使い、次は残りのビットのさらに半分を・・・、と
　　　キーのビット長さに合わせてxビットの幅を変えているため、より効率的となる
　　　・トライ木: キービット長/定数 => O(キービット長)
　　　・vEB木: log(キービット長)

　　・また、vEB木は各ノードで要素の最小値・最大値および、どの子ノードに要素が挿入されているかを管理しているため、
　　　(配列版のトライ木と異なり)有効な子ノードの検出が効率的に行える
　　　・子ノードの有効無効(要素の有無)を管理するためにも、vEB木が利用されている
　　　・bit-arrayを使った方が(環境によっては?)効率的になるかもしれない


==================
=== バージョン ===
・0.0.1


===========
=== API ===
# (veb-tree:make capacity) => tree
　veb木を作成する
　- capacity: 挿入される要素の最大値

# (veb-tree:size tree) => size
　veb木に挿入された要素の数を取得する

# (veb-tree:empty-p tree) => boolean
　veb木が空なら真を返す

# (veb-tree:push element tree) => tree
　veb木に要素を挿入する
　既に同じ要素が挿入されている場合は、要素の追加は行われない
　element: 正の整数値。make関数に渡したcapacity以内の値である必要がある

# (veb-tree:pop tree) => element
　veb木の先頭要素(一番小さい要素)を取り除いて返す

# (veb-tree:head tree) => element
　veb木の先頭要素を返す

# (veb-tree:remove element tree) => tree
　veb木から指定された要素を削除する

# (veb-tree:find element tree) => boolean
　veb木に指定された要素が存在するかどうかを判定する

# (veb-tree:next element tree) => element
　veb木内の存在するelement以上で一番小さい要素を返す
　該当する要素がない場合はnilが返る

# (veb-tree:to-list tree) => list
　veb木をリストに変換して返す
　返ってくるリストは、ソート済みの状態

# (veb-tree:from-list capacity tree) => tree
　veb木をリストから作成する

# (veb-tree:each (var tree &optional return-form) &body body)
　veb木内の各要素を昇順に走査する
　- var: 各走査で、要素が束縛される変数
　- tree: 走査対象のveb木
　- return-form: 走査終了後に評価される式。この式の評価結果がeachの返り値となる。
　- body: 各走査毎に実行される処理本体


============
=== 参考 ===
・http://en.wikipedia.org/wiki/Van_Emde_Boas_tree