g****v
发帖数: 971 | 1 Professor Bunyan thinks he has discovered a remarkable property of binary
search trees. Suppose that the search for key k in a binary search tree ends
up in a leaf.
Consider three sets: A, the keys to the left of the search path; B, the keys
on the search path; and C , the keys to the right of the search path.
Professor Bunyan claims that any three keys a \in A, b \in B, and c 2\in C
must satisfy a <= b <= c. Give a smallest possible counterexample to the
professor’s claim.
我怎么觉得是对的，实在是想不出counterexample。
哪位可以指点一下，谢谢。 | x******2
发帖数: 546 | 2 考虑一棵空的二叉搜索树，依次插入1,3,2,4
现在树上有4个元素，考虑k=4
于是A={2},B={1,3,4},C={}
就反例了 | g****v
发帖数: 971 | 3 C为空可以么，要求的是“any three keys”，如果为空的话，那就不是key了吧。 | x******2
发帖数: 546 | 4
晕，我只是举个例子而已，你可以变换一下C就不为空了呀
依次插入10,1,11,3,2,4, k=4
A={2},B={10,1,3,4},C={11}
【在 g****v 的大作中提到】
: C为空可以么，要求的是“any three keys”，如果为空的话，那就不是key了吧。
| f****4
发帖数: 1359 | 5 12
\
18
/ \
15 19
/ \
13 17
找17
A={13}, B={12,18,15,17}, C={19}
13>12 |
|
