BST 的时间复杂度
Time Complexity of BST
所以我知道由于结构减半，对 BST 的操作以对数时间运行，我想知道如果您搜索结构中不存在的值，时间复杂度是多少。
它仍然是 O(log n)。这样想，它会不断减半寻找，直到找不到。
平均情况时间复杂度为 O(log n)，最坏情况为 O(n)。要了解 O(log n) 复杂度，您可以参考 What does O(log n) mean exactly?
这张图片将向您解释部分：
我还建议您阅读 wiki 以了解详细信息。
所以我知道由于结构减半，对 BST 的操作以对数时间运行，我想知道如果您搜索结构中不存在的值，时间复杂度是多少。
它仍然是 O(log n)。这样想，它会不断减半寻找，直到找不到。
平均情况时间复杂度为 O(log n)，最坏情况为 O(n)。要了解 O(log n) 复杂度，您可以参考 What does O(log n) mean exactly?
这张图片将向您解释部分：
我还建议您阅读 wiki 以了解详细信息。