Van Emde Boas tree

ウィキペディア

Van Emde Boas木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/04 13:47 UTC 版)

van Emde Boas tree
種類	非二分木
発表時期	1975
発明者	Peter van Emde Boas
ビッグオー記法による計算量
アルゴリズム 平均 最悪の場合 空間 O(M) O(M) 探索 O(log log M) O(log log M) 挿入 O(log log M) O(log log M) 削除 O(log log M) O(log log M)

van Emde Boas 木 (オランダ語発音: [vɑn ˈɛmdə ˈboːɑs]) とは、m ビットの整数による連想配列を実現するための木構造である。オランダの計算機科学者 Peter van Emde Boas らによって 1975 年に開発された。探索・挿入・削除といった操作がすべて最悪計算量 O(log log M) で行える。

vEB 木の空間計算量は悪く、例えば、32 bit 整数を扱おうとすると、M=2³² ビットの記憶域が必要になってしまう。ただし、工夫すれば、扱う要素の数を n として O(n) の空間計算量を実現することもできる。

操作

vEB 木は、順序付き連想配列の機能を持ち、挿入・削除・検索の機能を持つ。また、これに加えて、与えられた数の周辺の要素の検索も可能である。^[1]

• 挿入：m ビットのキーと、対応する値のペアを挿入する
• 削除：与えられたキーを持つ要素を削除する
• 検索：キーから要素を検索する
• 後方検索：k 以上で最小のキーを持つ要素を検索する
• 前方検索：k 以上で最大のキーを持つ要素を検索する

さらに、vEB 木は最小値・最大値のクエリにも対応可能である。 最小値と最大値は木に変数として保存されているため、これらのクエリには O(1) で応答できる。

機能

1, 2, 3, 5, 8, 10 が挿入された後の vEB 木と、根が持つ補助構造の例

簡単のため、 log₂ m = k がある整数 ${\displaystyle k}$