data-structures - 为什么在二叉搜索树中查找是 O(log(n))？

Question

在 中查找值时，我可以看到如何BST 每次我们将一个节点与我们正在寻找的值进行比较时，我们都会留下一半的树。

但是我不明白为什么时间复杂度是 O(log(n)) .所以，我的问题是:

如果我们有一棵由 N 个元素组成的树，为什么查找树并检查特定值是否存在的时间复杂度是 O(log(n))，我们如何得到它？

Answer 1

您的问题似乎得到了很好的回答 here但总结一下你的具体问题，最好反过来考虑； “随着节点数量的增加，BST 求解时间会发生什么变化”？

本质上，在 BST 中，每次将节点数量增加一倍时，您只会将求解的步骤数增加一。为了扩展这一点，四倍的节点给出了两个额外的步骤。八倍的节点给出了三个额外的步骤。十六次节点给出了四个额外的步骤。等等。

这些对中第一个数字的基数为 2 的对数是这些对中的第二个数字。它是基数为 2 的日志，因为这是一个二分搜索(每一步都将问题空间减半)。