binary-tree - 不成功的二叉树搜索

Question

我知道对于成功的搜索，使用二叉树对包含 n 个键的所有输入的平均搜索时间在 Big O (lg n) 中，但是对于不成功的研究，这个结果是否成立？

Answer 1

严格来说，如果您的二叉树不平衡，即使成功搜索，您也可能无法获得 O(log n)。

对于平衡二叉树，很容易看出即使不成功，结果也会成立，因为在任何通用步骤中，您都可以排除剩余树的重要部分（大约一半）。

Answer 2

是的，二叉树结构允许您在每次检查时基本上丢弃一半的数据集。

想想你实际上必须访问多少个节点才能确定它不在那里。

例子：

     5
     /\
    3  8
   /\  /\
  1 4  6 9

假设你想要 2。从根开始，向左走，扔掉 8 和它的孩子。小于 3 所以向左扔掉 4。大于 1 所以它不存在。

在这种情况下，您只访问了 5、3 和 1。您可以将其视为与插入新节点相同。