t**********1
发帖数: 7 | 1 for a complete Binary Search Tree, write a search function to achieve < 2*
log(n) up bound on number of comparison operations. |
l*****a
发帖数: 14598 | 2 可以用汉语重复一下你的问题吗
2*
【在 t**********1 的大作中提到】
: for a complete Binary Search Tree, write a search function to achieve < 2*
: log(n) up bound on number of comparison operations.
|
t**********1
发帖数: 7 | |
l******4
发帖数: 729 | 4 BST不是一个比根节点小，另一个比根大吗？ 每一个搜索一次就够了，最什么左右都查
？ |
M***0
发帖数: 1180 | 5 用2个指针，一个走2步一个走1步直到走2步的那个走到头，则另一个在半中间，用这个
半中间的node和要查找到value比较，然后缩小一半范围继续找？ 思想类似binary
search |
I**A
发帖数: 2345 | 6 让不让用hashtable?
2*LOG（N）。
才能决定，搜索的数是 可能属于LEFT subtree, or right subtree, or equal.
【在 t**********1 的大作中提到】
:
|
s*******s
发帖数: 46 | 7 你可以这么办，如果<那么左边，如果>=则右边，
然后如果右边发现<,则说明是=（倒一层）
这样最多判断log(n)次
另外可以random判断<和>=的顺序，这样可以将最坏次数的概率减小。 |
