Van Emde Boas木
ウィキペディア フリーな encyclopedia
van Emde Boas 木 (オランダ語発音: [vɑn ˈɛmdə ˈboːɑs]) とは、m ビットの整数による連想配列を実現するための木構造である。オランダの計算機科学者 Peter van Emde Boas らによって 1975 年に開発された。探索・挿入・削除といった操作がすべて最悪計算量 O(log log M) で行える。
概要 種類, 発表時期 ...
van Emde Boas tree | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
種類 | 非二分木 | |||||||||||||||
発表時期 | 1975 | |||||||||||||||
発明者 | Peter van Emde Boas | |||||||||||||||
ビッグオー記法による計算量 | ||||||||||||||||
|
閉じる
vEB 木の空間計算量は悪く、例えば、32 bit 整数を扱おうとすると、M=232 ビットの記憶域が必要になってしまう。ただし、工夫すれば、扱う要素の数を n として O(n) の空間計算量を実現することもできる。