我想知道哪种平衡的 BST 很容易用 C++ 编码，并且仍然具有大致等于 O(logn) 的复杂度。
我已经尝试过红黑树，但想要一种代码不太复杂的替代方案。我过去曾与 Treaps 合作过，但我有兴趣探索性能更好或更易于实施的选项。
你有什么建议？
问问题
1254 次
1 回答
3
根据我的经验， AVL 树的性能通常比 Treaps 好，而且它们实施起来并不难。
它们通过旋转在任何插入或删除后变得不平衡的树的分支来工作。这保证了它们将具有完美的平衡，因此它们不会被奇怪的数据“欺骗”。
另一方面，Treaps 是随机分布的，这对于大型数据集来说是接近平衡的，但你仍然没有得到完美的 O(logn)。此外，您可能碰巧遇到以非常不平衡的方式插入的数据集，并且您的访问时间可能接近 O(n)。
查看维基百科页面了解更多信息：en.wikipedia.org/wiki/Avl_tree
于 2014-07-29T16:08:53.193 回答