edited by
22,712 views
54 votes
54 votes
A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain.

$\begin{array}{llllll} \text{(a)}  &  \text{61} & \text{52} & \text{14} &  \text{17} & \text{40} & \text{43} \\
 \text{(b)}  &  \text{2}&  \text{3} & \text{50} &  \text{40} & \text{60} & \text{43} \\
 \text{(c)}  &  \text{10} & \text{65} & \text{31} &  \text{48}&  \text{37} & \text{43} \\
 \text{(d)}  &  \text{81}  &\text{61} & \text{52} &  \text{14} & \text{41} & \text{43} \\
 \text{(e)}  &  \text{17} & \text{77} & \text{27} &  \text{66}&  \text{18} & \text{43}   \end{array}$
edited by

7 Answers

1 votes
1 votes

Case 1:

Consider the following example, If x < q, then we will only search the left subtree of q, and no element can be greater than q there, so if anything greater than x comes later in the left subtree that must be less than q. Now consider this relation recursively, so whenever we encounter an element that is greater than x, that must be less than the previous element greater than x we encountered. So all the elements greater than x we encounter during probing, that must be in a decreasing sorted order in a valid probe sequence.

 

Case 2:

Consider the following example, If x > q, then we will only search the right subtree of q, and no element can be less than q there, so if anything less than x comes later in the right subtree that must be greater than q. Now consider this relation recursively, so whenever we encounter an element that is less than x, that must be greater than the previous element less than x we encountered. So all the elements less than x we encounter during probing, that must be in a increasing sorted order in a valid probe sequence.

Conclusion

So our conclusion is that elements greater than x must be in a decreasing order and element less than x must be in an increasing order in a valid probe sequence searching for x.

Now apply the conclusion to the given options, we can clearly see that (b) has 60 coming after 50 and (e) has 18 coming after 27.

0 votes
0 votes

Here’s how I solve:

  1. Check if decision at every node is valid. ( for eg: if on a node 61, if we are searching for 43, we should go left.)
  2. Check if BST property at every node holds.

Thus, A,C,D are valid probe sequences.

Related questions

26 votes
26 votes
5 answers
1
Kathleen asked Oct 9, 2014
30,459 views
A binary search tree is generated by inserting in order the following integers:$$50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$$The number of nodes in the left subtree and ...
24 votes
24 votes
4 answers
2
29 votes
29 votes
3 answers
3
Kathleen asked Oct 9, 2014
12,131 views
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?$1$$3$$7$$8$
39 votes
39 votes
6 answers
4
Kathleen asked Oct 9, 2014
13,630 views
An advantage of chained hash table (external hashing) over the open addressing scheme isWorst case complexity of search operations is lessSpace used is lessDeletion is ea...