van Emde Boas tree
Common Lisp
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
.gitignore
README
package.lisp
veb-tree.asd
veb-tree.lisp

README

============
=== 概要 ===
・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