algorithm - 探戈树有实际应用吗？

Question

Balanced binary search tree给出 O(log(n)) 保证的搜索时间。

Tango trees实现了对 O(log(log(n)) 的搜索，同时牺牲了每个节点的少量内存。虽然我从理论角度理解 log(n) 和log(log(n)) 有很大的不同，对于大多数实际应用来说，它几乎没有任何优势。

例如，即使对于像 n = 10^20 这样的巨大数字(就像几千 PB)，log(n) = 64 和 之间的区别>log(log(n)) = 6 可以忽略不计。那么Tango树有没有什么实际用途呢？

Answer 1

tl;dr:不，改用拉伸(stretch)树。

Tango 树不会给您 O(log log n) 最坏情况查找——我认为平均情况是 O(log n log log n)。它们的运行速度最多比二叉树慢 O(log log n) 倍，而二叉树带有执行轮换以优化访问模式的 oracle。

Splay 树的运行速度可能比上述理论魔法树慢 O(1) 倍——这就是动态最优性猜想。 Splay trees 比 tango trees 简单得多，并且具有较低的启动常数因子。我无法想象探戈树保证会有用的实际应用。