D*****7
发帖数: 766 | 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 belonging to A, b belonging to B, and c
belonging to C must satisfy a <= b <= c. Give
a smallest possible counterexample to the professor’s claim.
教师手册上没给这题的答案，似乎是嫌它太简单。可我怎么也想不出来：（ | l******l
发帖数: 66 | 2 5
/
3
/ \
2 4
say the path is 5-3-2. 4 is to the right, but 4<5. | S****z
发帖数: 666 | 3 15
/
5
\
12
/ \
10 13
path 15-5-12-13
10 is to the left of the path, but 10 is > 5
in
keys
【在 D*****7 的大作中提到】
: 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 belonging to A, b belonging to B, and c
: belonging to C must satisfy a <= b <= c. Give
| D*****7
发帖数: 766 | |
|
