1. Given the following sequence of integers: 10, 17, 3, 90,
22, 7, 40, 15 2.
1. Starting with an empty binary search tree, insert this sequence of integers one at a time into this tree. Show the final tree. Assume that the tree will not keep any duplicates. This means when a new item is attempted to be inserted, it will not be inserted if it already exists in the tree.
2. How many item-to-item comparisons in all did it take to build this tree? (Assume one comparison for equality check, and another to branch left or right.)
3. SOLUTION
Following is the final tree.
comparisons for 1st item
10 // 0
4. 5.
6. 7.
8. 9.
comparisons 10.
11.
comparisons 12.
Total number of comparisons = 30
/\
3 17 //2
comparisons each for 3 and 17 \/\
7 15 90 //4 comparisons each for 7, 15, and 90
13.For the tree built in the above problem:
1. What is the worst case number of comparisons for a successful
search in this tree? For an unsuccessful (failed) search? (Assume one comparison for equality check, and another to branch left or right.)ANSWER
10
2. /\
3. 317
/
22 //6
\
40 //8
4.
5.
6.
7.
8.
9.
10. /\ 11. FF 12.
/\/\
F 7 15 90
/\/\/\ FFFF22 F
Note: The ‘F’ nodes are not actual tree nodes – they are failure positions.
▪ Successful search: 9 comparisons. (search for 40)
▪ Failed search: 10 comparisons (search for 23 thru 39, or
41 thru 89 – these will end up in one of the lowest level
leaf nodes marked ‘F’ in the tree above.
13.
14.What is the average case number of comparisons for a successful search in this tree?ANSWER
Average case number of comparisons for successful search:
10
comparison for match
15. /\ 16. 3 17
comparisons each for 3 and 17
17. \/\
// 1
// 3
18. 7 15 90 //5
comparisons each for 7, 15, and 90 19. /
20. comparisons
21. 22.
comparisons 23.
22
// 7 40 //9
Total number of comparisons = 1+2*3+3*5+7+9 = 38. Total number of successful search positions = 8. Assuming equal
/\
F 40
\
probabilities of search for all successful search positions,
average number of comparisons = 38/8.
24.
25.From this tree, delete 17: find the node (y) that has the smallest value in its right subtree, write y’s value over 17, and delete y. How much work in all (locating 17, then locating y , then deleting y) did it take to complete the deletion? Assume the following (a) you are using two pointers to navigate down the tree, a tracking pointer, and a lagging pointer, (b) 1 unit of work for an equality comparison between target and tree item, one for an inequality check to branch left or right, and 1 unit of work for a pointer assignment.
ANSWER
To delete 17, here is the work done:
▪ Locating 17: Number of comparisons is 3. Number of
pointer assignments is 4: to move two pointers (prev and ptr) down the tree, with 2 initial assignments (prev=null, ptr=@10), then 2 assignments to move to 17 (prev=@10, ptr=@17)
▪ Locating y: The smallest value in the right subtree of 17 is 22. Locating this requires 4 more pointer assignments for prev and ptr, to go from 17 to 90, then 90 and 22.But we also need to keep a pointer to 17, for the next step of writing y’s value in place of 17. So this is 1 more pointer assignment (e.g. x=ptr) If you didn’t count this, it’s ok since this extra pointer wasn’t explicitly stated in the question, which only mentioned two pointers.
▪ Overwriting 17 with 22: Not counted since there is no comparison or pointer assignment.
▪ Deleting y (22): One pointer assignment to set 90’s left child to @40.
26.So in all, comparisons=3, pointer assignments=4+4+1+1=10, for a total of 3+10=13 units of work.
14.
15.Given the following BST node class: public class BSTNode
16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.
Consider the following method to insert an item into a BST that
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38. 39.
BSTNode
int size;
…
public void insert(T target)
throws IllegalArgumentException {
BSTNode ptr=root, prev=null;
int c=0;
while (ptr != null) {
T data;
BSTNode
public BSTNode(T data) {
this.data = data;
this.left = null;
this.right = null;
}
public String toString() {
return data.toString();
}
}
does not allow duplicate keys:
extends Comparable
public class BST
…
57.
58.
59.
60.
61.
62.
63.
64.
root) 65.
66. 67. 68.
public void insert(T target)
throws IllegalArgumentException {
root = insert(target, root);
size++;
}
private BSTNode
throws IllegalArgumentException {
if (root == null) {
return new
}
BSTNode(target); 69.
70. 71.
72. 73.
74. 75.
}
if (c < 0) {
int c =
target.compareTo(root.data);
if (c == 0) {
throw new
IllegalArgumentException("Duplicate key");
76.
root.left); 77.
root.left = insert(target,
} else {
root.right =
78.
insert(target, root.right);
79. 80. 81. 82. 83.
}
return root;
}
84.* With the same BSTNode class as in the previous problem, write a method to count all entries in the tree whose keys are in a given range of values. Your implementation should make as few data comparisons as possible.
85.
entries in a BST whose keys are in a given range,
// Accumulates, in a given array list, all
86.
entries x such that min <= x <= max.
// including both ends of the range - i.e. all
87.
be filled with node data entries that make the cut.
95.
96. 97. 98.
if (root == null) {
return;
}
// The accumulation array list, result, will
88.
(initially empty) when this method is first called.
89. 90.
91. 92. 93. 94.
// The array list is already created
public static
void keysInRange(BSTNode
max, ArrayList
/* COMPLETE THIS METHOD */
}
SOLUTION
public static
void keysInRange(BSTNode
max, ArrayList
99. 100. 101.
<= max) 102.
103.
104.
105.
result); 106.
107. 108.
result); 109.
int c1 = min.compareTo(root.data);
int c2 = root.data.compareTo(max); if(c1<=0&&c2<=0){ //min<=root
result.add(root.data);
}
if (c1 < 0) {
keysInRange(root.left, min, max,
}
if (c2 < 0) {
keysInRange(root.right, min, max,
} 110.
} 111.
112.
113.With the same BSTNode class as in the previous problem, write a method that would take a BST with keys arranged in ascending order, and "reverse" it so all the keys are in descending order. For example: 25
25 114.
115. 116.
\ 117.
2 118.
119. 120.
/\ /\ 10 40 ---> 40 10
/\/\ /\/
2 2030 45 45 30 20
/\ /\ 15 35 35 15
121.
122.
123.
void reverseKeys(BSTNode
/* COMPLETE THIS METHOD */
The modification is done in the input tree itself, NO new tree is created. public static
124.
SOLUTION
public static
void reverseKeys(BSTNode
if (root == null) {
return;
}
reverseKeys(root.left);
reverseKeys(root.right);
BSTNode
root.left = root.right;
root.right = ptr;
}
136.* A binary search tree may be modified as follows: in every node, store the number of nodes in its right subtree. This modification is useful to answer the question: what is the k-th largest element in the binary search tree? (k=1 refers to the largest element, k=2 refers to the second largest element, etc.)You are given the following enhanced binary search tree node implementation:
125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135.
137.
{ 138. 139. 140.
public class BSTNode
T data;
BSTNode
int rightSize; // number of entries in
right subtree
141. 142. 143. 144.
Implement the following recursive method to find the k-th largest entry in a BST:
… }
145.
kthLargest(BSTNode
146. 147. 148. 149.
/* COMPLETE THIS METHOD */
}
150.
151.
152.
153.
154.
155.
156.
157.
158. 159.
public static
SOLUTION Assume root is not null, and 1 <= k < n
public static
T kthLargest(BSTNode
if (root.rightSize == (k-1)) {
return root.data;
}
if (root.rightSize >= k) {
return kthLargest(root.right, k);
}
return kthLargest(root.left, k-
root.rightSize-1);
}