我想知道哪种平衡 BST 易于用 C++ 编码，并且复杂度仍大致等于 O(logn)。
我已经尝试过红黑树，但想要一种代码不那么复杂的替代方法。我过去曾使用过 Treaps，但我有兴趣探索性能更好或更易于实现的选项。
你有什么建议？
最佳答案
根据我的经验，
AVL 树通常比 Treap 表现得更好，而且实现起来并不难。
它们通过旋转在任何插入或删除后变得不平衡的树分支来工作。这保证了它们将具有完美的平衡，因此它们不会被奇怪的数据“欺骗”。
另一方面，Treaps 是随机分布的，对于大型数据集来说接近平衡，但您仍然无法获得完美的 O(logn)。此外，您可能恰好遇到以非常不平衡的方式插入的数据集，并且您的访问时间可能接近 O(n)。
查看维基百科页面了解更多信息:en.wikipedia.org/wiki/Avl_tree
关于c++ - 对于易于编码的平衡二叉搜索树，我应该选择什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24981891/