Существует ли какое-либо практическое применение Tango Trees?

Сбалансированное дерево двоичного поиска дает O(log(n)) гарантированное время поиска.

Tango trees обеспечивает поиск O(log(log(n)), одновременно снижая объем памяти на node. Хотя я понимаю, что с теоретической точки зрения log(n) и log(log(n)) имеет огромное значение, для большинства практических приложений это практически не дает преимуществ.

Например, даже для огромного числа, такого как n = 10^20 (которое составляет несколько тысяч петабайт), разница между log(n) = 64 и log(log(n)) = 6 довольно незначительна. Итак, есть ли практическое использование дерева танго?

Ответы

Ответ 1

tl; dr: no, вместо этого используйте дерево воспроизведения.

Деревья танго не дают вам O (log log n) наихудшие поисковые запросы - средний случай - я думаю, O (log n log log n). То, что они делают, выполняется не более O (log log n) раз медленнее, чем двоичное дерево с оракулом, который выполняет вращения для оптимизации шаблонов доступа.

Деревья Splay могут запускать O (1) раз медленнее, чем вышеупомянутое теоретическое магическое дерево - это гипотеза динамической оптимальности. Деревья Splay намного проще, чем деревья танго, и будут иметь более низкие постоянные факторы для загрузки. Я не могу представить себе практическое приложение, в котором гарантирована гарантия танго.