我知道对于成功的搜索,使用二叉树对包含 n 个键的所有输入的平均搜索时间在 Big O (lg n) 中,但是对于不成功的研究,这个结果是否成立?
问问题
387 次
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 回答