如何计算在 AVL 树中搜索的时间复杂度？
How to calculate the time complexity of searching in an AVL tree?
我知道 AVL 树搜索算法的时间复杂度是 O(log n) 但它是如何推导出来的？
这样想。在树中的每个节点，您基本上有三个选项：
- 您已找到搜索关键字，可以结束搜索
- 继续在左子树中搜索（如果有的话）
- 继续在右子树中搜索（如果有的话）
在每个步骤的最后，您基本上将问题分成两半并丢弃其中的一部分。这意味着在每个步骤结束时，您只剩下该步骤之前的问题集的一半。
这类似于二进制搜索的工作方式。
这就解释了 log n 时间复杂度。
我知道 AVL 树搜索算法的时间复杂度是 O(log n) 但它是如何推导出来的？
这样想。在树中的每个节点，您基本上有三个选项：
- 您已找到搜索关键字，可以结束搜索
- 继续在左子树中搜索（如果有的话）
- 继续在右子树中搜索（如果有的话）
在每个步骤的最后，您基本上将问题分成两半并丢弃其中的一部分。这意味着在每个步骤结束时，您只剩下该步骤之前的问题集的一半。 这类似于二进制搜索的工作方式。
这就解释了 log n 时间复杂度。