1. 2.
Problem Set 6 – Solution Binary Search Tree (BST)
Given the following sequence of integers: 10, 17, 3, 90, 22, 7, 40, 15
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.
4. 5.
6. 7.
SOLUTION
Following is the final tree.
comparisons for 1st item
10 //0
/\
3 17 //2
comparisons each for 3 and 17 \/\
7 15 90 //4 comparisons each for 7, 15, and 90
8. /
9.
comparisons
10.
11.
comparisons
12.
Total number of comparisons = 30
22
//6 40 //8
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
\
▪ ▪
10
comparison for match
15. /\ 16. 3 17
comparisons each for 3 and 17
17. \/\ 18. 7 15 90
// 1 // 3 //5 // 7 //9
comparisons each for 7, 15, and 90
19. 20.
comparisons
21.
22.
comparisons
23.
/ 22
Total number of comparisons = 1+2*3+3*5+7+9 = 38. Total number of successful search positions = 8. Assuming equal probabilities of search for all successful search positions, average number of comparisons = 38/8.
24.
/\ 317
2.
3.
4.
5.
6.
7.
8.
9.
10. /\ 11. FF 12.
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:
/\/\
F 7 15 90
/\/\/\ FFFF22 F
/\
F 40
\ 40
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. (Move prev and ptr from 17 to 90, then 90 and 22.) 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=9, for a total of 3+9=12 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.
T data;
BSTNode
public BSTNode(T data) {
this.data = data;
this.left = null;
this.right = null;
}
public String toString() {
return data.toString();
}
▪
▪
▪
▪
Consider the following method to insert an item into a BST that does
not allow duplicate keys: public class BST
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38. if (c == 0) {
39. throw new
IllegalArgumentException(“Duplicate key”);
40. }
41. prev = ptr;
42. ptr=c<0 ? ptr.left :
ptr.right;
43. }
44. BSTNode tmp = new BSTNode(target);
45. size++;
46. if (root == null) {
BSTNode
int size;
…
public void insert(T target)
throws IllegalArgumentException {
BSTNode ptr=root, prev=null;
int c=0;
while (ptr != null) {
c= target.compareTo(ptr.data);
47. 48.
49. }
50. if(c<
51.
52. } else {
53.
54. }
55. }
56.
root = tmp;
return;
0){
prev.left = tmp;
prev.right = tmp;
57.
58.
59.
60.
61.
62.
public class BSTN
…
public void insert(T target)
throws IllegalArgumentException {
Write a recursive version of this method, using a helper method if necessary.SOLUTION
}
root = insert(target, root);
size++;
63. 64.
root) 65.
66.
67.
68.
69.
70.
71.
72.
73.
74. 75. 76.
root.left);
77.
78.
root.right);
79.
80.
81. } 82.
83.
private BSTNode
throws IllegalArgumentException {
if (root == null) {
return new BSTNode(target);
}
int c = target.compareTo(root.data);
if (c == 0) {
throw new
IllegalArgumentException(“Duplicate key”);
}
if (c < 0) {
root.left = insert(target,
} else {
root.right = insert(target,
}
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. // Accumulates, in a given array list, all
entries in a BST whose keys are in a given range,
86. // including both ends of the range - i.e. all
entries x such that min <= x <= max.
87. // The accumulation array list, result, will be
filled with node data entries that make the cut.
88. // The array list is already created (initially
empty) when this method is first called.
89. public static
90. void keysInRange(BSTNode
ArrayList
91. /* COMPLETE THIS METHOD */ 92.
93. }
94.
SOLUTION
public static
95. void keysInRange(BSTNode
ArrayList
96. if (root == null) {
97. return;
98. }
99. int c1 = min.compareTo(root.data);
100. int c2 = root.data.compareTo(max);
101. if(c1<=0&&c2<=0){ //min<=root<=
max)
102. result.add(root.data);
103. }
104. if (c1 < 0) {
105. keysInRange(root.left, min, max, result);
106. }
107. if (c2 < 0) {
108. keysInRange(root.right, min, max,
result); 109. } 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. 10 40 ---> 40 10 116. /\/\ /\/\ 117. 2 2030 45 45 30 20 2 118./\ /\ 119. 15 35 35 15
120.
The modification is done in the input tree itself, NO new tree is
created. public static
122. 123. 124.
/* COMPLETE THIS METHOD */
SOLUTION
public static
125. void reverseKeys(BSTNode
126.
127.
128.
129.
130.
131.
132.
133.
134. } 135.
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:
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. public static
kthLargest(BSTNode
146. /* COMPLETE THIS METHOD */ 147. }
148.
149.
SOLUTION Assume root is not null, and 1 <= k < n
public static
150.
151.
152.
153.
154.
155.
156.
157.
158. } 159.
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);
Problem Set 7 – Solution AVL Tree
1.* Each node of a BST can be filled with a height value, which is the height of the subtree rooted at that node. The height of a node is the
maximum of the height of its children, plus one. The height of an empty tree is -1. Here’s an example, with the value in parentheses indicating the height of the corresponding node:
P(3)
2. 3. 4. 5. 6. 7. 8.
/\ M(1) V(2)
//\ A(0) R(1) X(0)
\ S(0)
Complete the following recursive method to fill each node of a BST with its height value. public class BSTNode
9.
10.
11.
12.
13.
14.
15.
16. 17. 18. 19. 20. 21.
SOLUTION
// Recursively fills height values at all nodes of
a binary tree
T data;
BSTNode
int height;
…
}
// Recursively fills height values at all nodes
of a binary tree
public static
void fillHeights(BSTNode
// COMPLETE THIS METHOD
… }
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
public static
void fillHeights(BSTNode root) {
if (root == null) { return; }
fillHeights(root.left);
fillHeights(root.right);
root.height = -1;
if (root.left != null) {
root.height = root.left.height;
}
if (root.right != null) {
root.height = Math.max(root.height,
root.right.height);
33. 34. 35. 36.
37.In the AVL tree shown below, the leaf “nodes” are
actually subtrees whose heights are marked in parentheses: —— D ——-
}
root.height++;
}
38.
39.
40.
41.
42.
43.
44.
45.
2. Mark the balance factor of each node. 46.SOLUTION
Heights/Balance factors
A:h+1/right, C:h/equal, E:h+2/left, G:h+1/equal, B:h+2/left, F:h+3/ left, D:h+4/right
Height of the tree is h+4
47.
48.Given the following AVL tree: —J—
/\ BF
/\/\ ACEG
/\/\/\/\ T1T2T3T4 T5T6T7T8
(h-1) (h) (h-1) (h-1) (h+1) (h) (h) (h)
1. Mark the heights of the subtrees at every node in the tree. What is the height of the tree?
49. 50. 51. 52. 53. 54. 55. 56. 57. 58.
/\ FT
/\/\ CHNX
/\/\/ BELQV
/\ OS
1. Determine the height of the subtree rooted at each node in the tree.
2. Determine the balance factor of each node in the tree.
3. Show the resulting AVL tree after each insertion in the following sequence: (In all AVL trees you show, mark the balance factors next to the nodes.)
59.SOLUTION
1 and 2:
60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75.
3:
Node Height
Balance factor
▪ Insert Z ▪ Insert P ▪ Insert A
————————————– B0- E0- C1- F2/ H0- O0- S0- Q1- L0- N2\ V0- X1/ T3/ J4\
1. After Inserting Z:
J— 2.
3. 4. 5. 6. 7.
– 8.
9. 10. 11.
—
13.
14.
15.
16.
17.
18.
– 19.
20. 21. 22. 23. ▪
/\ FT
/\/\ CHN\X-
/\/\/\ BE L/QVZ
/\ \OS
\ -P
Only the balance factors of Z and X are changed; others remain the same
12.After inserting P (in the tree above): —J—
Insert P as the right child of O
▪ SetbfofPto’-‘
▪ BackuptoOandsetbf’\’
▪ BackuptoQandsetbfto’/’
▪ Back up to N and stop. N is unbalanced, so rebalance at N.
24.Rebalancing at N is Case 2.
▪ First, rotate O-Q —J—
▪/\ ▪FT
▪ /\/\
/\ FT
/\/\ CHNX-
/\/\/\ BE LQVZ
/\ OS
▪ ▪ ▪
X-
\
CHN\ /\/\/ BELOV
Z- ▪\ ▪Q ▪/\ ▪-P
S ▪
▪ Then, rotate O-N —J—
▪/\ ▪FT
▪ /\/\ ▪
X- \ Z-
▪
▪ ▪
25.
26.After inserting A (in the tree above):
—J— 27.
28.
29.
30.
31.
32.
– 33. 34. 35.
C H O- /\/\/
▪ ▪
B E
/N -Q V
//\ -L -P S
-A
/\ FT
/\/\
/C H O- X- /\/\/\
/B E /N -Q V Z
///\ -L – P S
76.
▪ Insert A as the left child of B
▪ SetbfofAto’-‘
▪ BackuptoBandsetbfto’/’
▪ BackuptoCandsetbfto’/’
▪ Back up to F and stop. F is unbalanced, so rebalance at F.
36.Rebalancing at F is Case 1.
▪ Rotate C-F — J—
▪/\ ▪ -CT
▪ ▪
▪ ▪
▪
▪ ▪
/\/\ /B-F O-
//\/\/ -A -EH-/N -Q V
//\ -L -P S
X- \ Z-
77.Starting with an empty AVL tree, the following sequence of keys are inserted one at a time: 1, 2, 5, 3, 4
78.
Assume that the tree allows the insertion of duplicate keys.What is the total units of work performed to get to the final AVL tree, counting only key-to-key comparisons and pointer assignments? Assume each comparison is a unit of work and each pointer assignment is a unit of work. (Do not count pointer assignments used in traversing the tree. Count only assignments used in changing the tree structure.)
SOLUTION
Since the tree allows duplicate keys, only one comparison is needed at every node to turn right (>) or left (not >, i.e. <=) when descending to insert.
1. To insert 1: 0 units 1 2.
3. To insert 2: 1 comparison + 1 pointer assignment = 2 units
1
4. 5. 6.
\ 2
7. To insert 5: 2 comparisons + 1 pointer assignment:
1
root=2, 2
8. 9. 10. 11. 12.
\ 2
\ 5
Then rotation at 2-1, with 3 pointer assignments:
2.left=1, 1.right=null 13.
Total: 2+1+3 = 6 units, resulting in this tree:
14. 15. 16.
/\ 15
17.To insert 3: 2 comparisons + 1 pointer assignment = 3 units: 2
18. 19. 20. 21. 22.
23.To insert 4: 3 comparisons + 1 pointer assignment: 2
24. 25. 26. 27. 28. 29. 30.
Then a rotation at 4-3, with 3 pointer assignments: 2
31. 32.
33.
34.
35.
36.
/ 4
/\ 15
/ 3
/\ 15
/ 3
\ 4
/\
3.right=null, 4.left=3
1
/ 3
5 Pointer assignments: 5.left=4,
93.
94.
95.
96.
public static
void rotateCase1(AVLTreeNode
// r is root of taller subtree of x
r = x.balanceFactor == ‘\’ ? x.right : x.left;
if (x.parent.left == x) { x.parent.left = r; }
97.
r.parent = x.parent;
37.
And a rotation at 4-5, with 3 pointer assignments: 2
38. 39.
SOLUTION
/\
4.right=5, 5.left=null
1
Total: 10 units 79.Grand total: 21 units of work
80.* After an AVL tree insertion, when climbing back up toward the root, a node x is found to be unbalanced. Further, it is determined
that x’s balance factor is the same as that of the root, r of its taller subtree (Case 1). Complete the following rotateCase1 method to perform the required rotation to rebalance the tree at node x. You may assume that x is not the root of the tree. public class AVLTreeNode
81. 82. 83.
‘\’ 84.
85. 86. 87. 88. 89. 90. 91. 92.
public T data;
public AVLTreeNode
40. 41. 42.
/\ 35
4 Pointer assignments: 2.right=4,
public char balanceFactor;
public AVLTreeNode
// ‘-‘ or ‘/’ or
public int height;
}
public static
void rotateCase1(AVLTreeNode
// COMPLETE THIS METHOD
}
else { x.parent.right = r; }
98. counter-clockwise
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
AVLTreeNode temp = r.left;
r.left = x;
x.parent = r;
x.right = temp;
x.right.parent = x;
} else { // rotate clockwise
AVLTreeNode temp = r.right;
r.right = x;
x.parent = r;
x.left = temp;
x.left.parent = x;
}
// change bfs of r and x
x.balanceFactor = ‘-‘;
r.balanceFactor = ‘-‘;
// x’s height goes down by 1, r’s is
unchanged
115. 116. 117. 118.
if (x.balanceFactor == ‘\’) { // rotate
x.height–;
}