Sal*_*ali 8 algorithm tree complexity-theory
平衡二叉搜索树提供有O(log(n))保证的搜索时间.
Tango树实现了搜索,O(log(log(n))同时损害了每个节点的少量内存.虽然我从理论的角度理解log(n)并且log(log(n))产生了巨大的差异,但对于大多数实际应用来说,它几乎没有任何优势.
例如,即使对于像一个巨大的数字n = 10^20(就像几千PB级)之间的区别log(n) = 64和log(log(n)) = 6是相当微不足道的.那么Tango树有什么实际用途吗？
tl; dr：不，请改用张开树。
探戈树不会给你 O(log log n) 最坏情况的查找——我认为平均情况是 O(log n log log n)。他们所做的最多比二叉树慢 O(log log n) 倍，二叉树执行旋转以优化访问模式。
展开树的运行速度可能比前面提到的理论魔法树慢 O(1) 倍——这就是动态最优性猜想。展开树比探戈树简单得多，而且要启动的常数因子也更低。我无法想象探戈树保证会有用的实际应用。