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.
9.
10. BSTNode
11. int height;
12. …
13. }
14.
15. // Recursively fills height values at all nodes
of a binary tree
/\ 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
16.
17.
18.
19.
20. } 21.
22.
23.
24.
25.
public static
void fillHeights(BSTNode root) {
if (root == null) { return; }
fillHeights(root.left);
T data;
public static
void fillHeights(BSTNode
// COMPLETE THIS METHOD
…
SOLUTION
// Recursively fills height values at all nodes
of a binary tree
26. fillHeights(root.right);
27. root.height = -1;
28. if (root.left != null) {
29. root.height = root.left.height;
30. }
31. if (root.right != null) {
32. root.height = Math.max(root.height,
root.right.height);
33. }
34. root.height++;
35. } 36.
37.In the AVL tree shown below, the leaf “nodes” are
actually subtrees whose heights are marked in parentheses: —— D ——-
38. / \ 39. B F
40.
41.
42.
43.
44.
(h)
/\ /\ ACEG
/\/\/\/\ T1T2T3T4 T5T6T7T8
(h-1) (h) (h-1) (h-1) (h+1) (h) (h)
45.
1. Mark the heights of the subtrees at every node in the tree.
What is the height of the tree?
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—
49. 50. 51. 52. 53. 54. 55. 56. 57. 58.
/\ FT
/\/\ CHNX
/\/\/ BELQV
/\ OS
Determine the height of the subtree rooted at each node in the tree.
Determine the balance factor of each node in the tree.
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.)
1.
2. 3.
Insert Z Insert P Insert A
Node Height
60.
61. B 0 –
62. E 0 –
63. C 1 –
64. F 2 /
65. H 0 –
66. O 0 –
67. S 0 –
68. Q 1 –
69. L 0 –
70. N 2 \
59.SOLUTION 1 and 2:
▪ ▪ ▪
Balance factor
————————————–
71. V 0 – 72. X 1 / 73. T 3 / 74. J 4 \ 75.
3:
1.
2.
3.
4.
5.
6.
7.
8. 9. 10. 11.
After Inserting Z:
—J—
–
/\ FT
/\/\ CHNX-
/\/\/\ BE LQVZ
/\ OS
Only the balance factors of Z and X are changed; others remain the same
12.After inserting P (in the tree above): —J—
13.
14.
15.
16.
17.
18.
– 19.
20.
21.
22.
23.
/\ FT
/\/\ CHN\X-
/\/\/\ BE L/QVZ
/\ \OS
\ -P
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 ▪ /\/
\
▪ CHN\
X- ▪/\/\
/\ ▪BELO
VZ- ▪\ ▪
Q ▪/
\ ▪-P
S ▪
▪ Then, rotate O-N —J—
▪/\ ▪FT ▪ /\/
\
C H O-
X- ▪/\/\
/\
▪
▪
▪ ▪
▪
25.
26.After inserting A (in the tree above): —J—
BE /N-Q
//\ -L -P
35.
▪ Insert A as the left child of B ▪ SetbfofAto’-‘
▪ BackuptoBandsetbfto’/’
▪ ▪
BackuptoCandsetbfto’/’
Back up to F and stop. F is unbalanced, so rebalance at F.
VZ- S
27.
28.
29.
30.
31.
32.
–
33.
34. -A
/\ FT
/\/\
/C H O- X- /\/\/\
/B E /N -Q V Z
///\ -L – P S
36.Rebalancing at F is Case 1.
▪ Rotate C-F —J—
▪/\ ▪ -CT ▪/\/
▪
\ X-
/B-F O-
▪
76.
▪ //\/\ /\
▪
▪
-A -EH-/N -Q ▪ //\
VZ- S
-L -P
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. 2
6.
7. To insert 5: 2 comparisons + 1 pointer assignment: 1
8. \ 9. 2
10. \ 11.
12.
5
Then rotation at 2-1, with 3 pointer assignments:
root=2, 2.left=1, 1.right=null 13.
Total: 2+1+3 = 6 units, resulting in this tree: 2 14. /\
15. 1 5 16.
17.To insert 3: 2 comparisons + 1 pointer assignment = 3 units: 2
18. /\ 19. 1 5 20. / 21. 3 22.
23.To insert 4: 3 comparisons + 1 pointer assignment: 2 24. /\
25. 1 5
26. 27. 28. 29. 30.
/ 3
\ 4
Then a rotation at 4-3, with 3 pointer assignments: 2 31. /\
32. 1 5 Pointer assignments: 5.left=4,
3.right=null, 4.left=3
33. / 34. 4 35. / 36. 3 37.
And a rotation at 4-5, with 3 pointer assignments: 2 38. /\
39. 1 4 Pointer assignments: 2.right=4,
4.right=5, 5.left=null
40. /\
41. 3 5
42.
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. public T data;
82. public AVLTreeNode
83. public char balanceFactor;
or ‘\’
84. public AVLTreeNode
85. public int height;
86. } 87.
// ‘-‘ or ‘/’
88. 89. 90. 91. 92.
public static
void rotateCase1(AVLTreeNode
// COMPLETE THIS METHOD
}
93. 94. 95.
void rotateCase1(AVLTreeNode
// r is root of taller subtree of x
r = x.balanceFactor == ‘\’ ? x.right :
SOLUTION public static
x.left;
96. if (x.parent.left == x) { x.parent.left =
r; } else { x.parent.right = r; }
97. r.parent = x.parent;
98. if (x.balanceFactor == ‘\’) { // rotate
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. x.height–; 116.
117. }
118.