Что препятствует тому, чтобы деревья Ван Эмде Боаса стали более популярными в реальных приложениях?

Мы знаем, что сбалансированные деревья выполняют вставку, удаление и поиск в O (log n) -time, примеры включают

Красно-черный
AVL
Splay
B-дерево (и его варианты).

Однако, когда ключи являются целыми числами в ограниченном диапазоне, можно использовать дерево Van Emde Boas для переноса этих операций до O (log (log n)) - время, то есть экспоненциально лучше, чем деревья AVL или RB, Ну, это на самом деле случай многих приложений в реальном мире.

Я вижу много приложений для этого. Один из них, который я хотел бы привести, - это базы данных, для которых создание индексов в основном предполагает выбор между хешем или B * -tree. Если бы дерево Van Emde Boas было реализовано, это обеспечило бы половину между этими двумя вариантами, теоретически улучшив многие проблемы оптимизации запросов.

Почему дерево Van Emde Boas широко не используется, как говорят Red-Black или B-tree, поскольку

это не новинка (она была изобретена в 1975 году).
легко реализовать
быстрее, чем другие деревья

и каковы соображения об этом?

Ответ 1

Асимптотическая сложность иногда вводит в заблуждение. В случае Van Emde Boas tree константа довольно велика см. Здесь. Я цитирую:

However, for small trees the overhead associated with vEB trees
is enormous: on the order of 2^(m/2)

Существуют и другие случаи, когда существует алгоритм с лучшей сложностью, но он только улучшается для ввода настолько большого, что на практике он почти никогда не используется, например. линейное статическое время RMQ.

Ответ 2

Одна из причин заключается в том, что сложность определяется не размером хранимого вами набора, а размером юниверса значений. Другое отличие состоит в том, что ключи не могут быть произвольными типами, для которых у вас есть операция сравнения, но должны быть целыми числами. Вы не должны видеть vEB в качестве альтернативы для BST, а скорее как альтернативу для массивов. Массив имеет O (1), чтобы хранить и искать затраты для объекта, на который ссылаются целые числа. vEB предлагает O (log log M), где M - размер юниверса ваших значений. Теперь вы видите, что vEB не лучше обычного массива для поиска и сохранения, но он предлагает операции O (1) min, max и O (log log M) prev следующих ключевых операций, в которых нет массива. Стоит отметить, что компоновка деревьев vEB имеет свойства, которые позволяют создавать кэшированные забытые деревья, которые являются гораздо более интересными разработками современной CS.

http://erikdemaine.org/papers/BRICS2002/paper.pdf