0

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

4

2 回答 2

1

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

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

于 2016-05-06T02:15:43.950 回答
0

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

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

例子:

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

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

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

于 2016-05-06T02:26:22.780 回答