Van Emde Boas tree とは

vEBツリーとも呼ばれるVan Emde Boasツリー(またはVan Emde Boas優先キュー、オランダの発音:[vɑn 'ɛmdə'boːɑs])は、mビットの整数キーを持つ連想配列を実装するツリーデータ構造です。これは、O(ログm)時間、またはO(ログログM)時間ですべての操作を実行します。ここで、M = 2mはツリーに格納できる要素の最大数です。 Mはツリーに格納されている要素の実際の数と混同してはなりません。これにより他のツリーデータ構造のパフォーマンスが測定されることがよくあります。 vEBツリーは、以下に説明するように、多数の要素を含む場合、良好な空間効率を有する。それは、1975年にオランダのコンピュータ科学者Peter van Emde Boasが率いるチームによって発明されました。