探戈树有实际应用吗？ [英] Is there any practical application of Tango Trees?

问题描述

平衡的二进制搜索树给出了 O（log（ n））保证搜索时间。

Balanced binary search tree gives an O(log(n)) guaranteed search time.

探戈树实现了 O（log（log（n））的搜索，同时损害了每个节点的少量内存。理论观点 log（n）和 log（log（n））产生了很大的变化，

Tango trees achieves a search of O(log(log(n)) while compromising small amount of memory per node. While I understand that from theoretical point of view log(n) and log(log(n)) makes a huge difference, for majority of practical applications it provides almost no advantage.

例如，即使对于像 n = 10 ^ 20 （就像几千PB） log（n）= 64 和 log（log（n））= 6

For example even for a huge number like n = 10^20 (which is like few thousand petabytes) the difference between log(n) = 64 and log(log(n)) = 6 is pretty negligible. So is there any practical usage of a Tango tree?

推荐答案

tl; dr：不，使用a

tl;dr: no, use a splay tree instead.

探戈树不会给你O（log log n）最差的结果案例查找-平均情况是我认为O（log n log log n）。它们执行的操作比使用带有执行轮换以优化访问模式的预言的二叉树的运行速度最多慢O（log log n）倍。

Tango trees don't give you O(log log n) worst case lookups -- the average case is I think O(log n log log n). What they do is run at most O(log log n) times more slowly than a binary tree with an oracle that performs rotations to optimize the access patterns.

展开树可能比前面提到的理论魔术树慢O（1）倍-这是动态最优性猜想。八字树比探戈树简单得多，并且具有较低的引导常数因子。我无法想象在探戈树保证中有用的实际应用。

Splay trees might run O(1) times more slowly than the aforementioned theoretical magic tree -- this is the Dynamic Optimality conjecture. Splay trees are much simpler than tango trees and will have lower constant factors to boot. I can't imagine a practical application where the tango tree guarantee would be useful.

这篇关于探戈树有实际应用吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！