algorithm - 平衡 BST 的最佳和最坏情况搜索性能是什么？

Question

平衡 BST 的最佳和最坏情况搜索性能是什么？每种情况发生时如何用一句话解释？

标签： algorithmdata-structures

Answer 1

沿着从根到叶子的路径进行搜索，叶子在平衡树中的长度为 Log n。

最佳情况：命中第一个节点，O(1)*。

最坏情况：命中最后一个节点，O(Log n)。

---

如果实现执行相等性测试，这是真的，允许提前终止。否则，在所有情况下都将遵循完整路径。