Дерево ван Эмде Боаса

Дерево ван Эмде Боаса (англ. Van Emde Boas tree, vEB tree) --- структура данных, представляющая собой дерево поиска, позволяющее хранить произвольные подмножества целых неотрицательных чисел из интервала [math]\displaystyle{ [0, 2^k) }[/math].

Особенностью этой структуры является то, что она поддерживает хранение чисел в их двоичном представлении и позволяет выполнять над ними все соответствующие дереву поиска операции за время [math]\displaystyle{ O(\log k) }[/math], что асимптотически лучше, чем время [math]\displaystyle{ O(\log n) }[/math], требуемое на их выполнение в большинстве других деревьев поиска, где [math]\displaystyle{ n }[/math] --- количество элементов в дереве.