平衡二叉搜索树 http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree给出一个O(log(n))保证搜索时间。
探戈树 https://en.wikipedia.org/wiki/Tango_tree实现搜索O(log(log(n))同时牺牲每个节点的少量内存。虽然我从理论角度理解log(n) and log(log(n))产生巨大的差异，对于大多数实际应用来说它几乎没有提供任何优势。
例如，即使对于像这样的巨大数字n = 10^20（大约几千拍字节）之间的区别log(n) = 64 and log(log(n)) = 6是相当可以忽略不计的。那么 Tango 树有什么实际用途吗？
tl;dr：不，请使用展开树。
Tango 树不会给你 O(log log n) 最坏情况查找——我认为平均情况是 O(log n log log n)。它们的运行速度最多比带有预言机的二叉树慢 O(log log n) 倍，预言机执行轮换以优化访问模式。
展开树的运行速度可能比前面提到的理论魔法树慢 O(1) 倍——这是动态最优猜想。八字树比探戈树简单得多，并且启动的常数因子也较低。我无法想象探戈树保证在实际应用中会有用。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
