论文标题
不平衡的二进制树
Unbalancing Binary Trees
论文作者
论文摘要
假设ZIPF定律是准确的，我们表明，部分优化二进制树的现有技术产生的结果比真正的最佳效果差10％。我们提出了一种新的近似优化技术，该技术在O（n log n）时间内运行，并产生比最佳差约1％的树。运行时间与GARSIA-WACHS算法的运行时间相当，但是该技术可以应用于更有用的情况，在此情况下，搜索的节点预计将包含在树中，而不是外部。
Assuming Zipf's Law to be accurate, we show that existing techniques for partially optimizing binary trees produce results that are approximately 10% worse than true optimal. We present a new approximate optimization technique that runs in O(n log n) time and produces trees approximately 1% worse than optimal. The running time is comparable to that of the Garsia-Wachs algorithm but the technique can be applied to the more useful case where the node being searched for is expected to be contained in the tree as opposed to outside of it.
