Due to the print book page limit, we cannot inlcude all good CheckPoint questions in the physical book. The CheckPoint on this Website may contain extra questions not printed in the book. The questions in some sections may have been reordered as a result. Nevertheless, it is easy to find the CheckPoint questions in the book on this Website. Please send suggestions and errata to Dr. Liang at y.daniel.liang@gmail.com. Indicate the book, edition, and question number in your email. Thanks!

Chapter 26 Check Point Questions

Section 26.2
▼26.2.1
What is an AVL tree? Describe the following terms: balance factor, left-heavy, and right-heavy.
▼26.2.2
Show the balance factor of each node in the trees shown in Figure 26.1.
▼26.2.3
Describe LL rotation, RR rotation, LR rotation, and RL rotation for an AVL tree.
Section 26.3
▼26.3.1
What are the data fields in the AVLTreeNode class?
▼26.3.2
True or false: AVLTreeNode is a subclass of TreeNode?
▼26.3.3
True or false: AVLTree is a subclass of BST.
Section 26.4
▼26.4.1
For the AVL tree in Figure 26.1a, show the new AVL tree after adding element 40. What rotation do you perform in order to rebalance the tree? Which node was unbalanced?
▼26.4.2
For the AVL tree in Figure 26.1a, show the new AVL tree after adding element 50. What rotation do you perform in order to rebalance the tree? Which node was unbalanced?
▼26.4.3
For the AVL tree in Figure 26.1a, show the new AVL tree after adding element 80. What rotation do you perform in order to rebalance the tree? Which node was unbalanced?
▼26.4.4
For the AVL tree in Figure 26.1a, show the new AVL tree after adding element 89. What rotation do you perform in order to rebalance the tree? Which node was unbalanced?
Section 26.5
▼26.5.1
Use Listing 26.2 as a template to describe the algorithms for implementing the RR, LR, and RL rotations.
Section 26.6
▼26.6.1
For the AVL tree in Figure 26.1a, show the new AVL tree after deleting element 107. What rotation do you perform in order to rebalance the tree? Which node was unbalanced?
▼26.6.2
For the AVL tree in Figure 26.1a, show the new AVL tree after deleting element 60. What rotation do you perform in order to rebalance the tree? Which node was unbalanced?
▼26.6.3
For the AVL tree in Figure 26.1a, show the new AVL tree after deleting element 55. What rotation did you perform in order to rebalance the tree? Which node was unbalanced?
▼26.6.4
For the AVL tree in Figure 26.1b, show the new AVL tree after deleting elements 67 and 87. What rotation did you perform in order to rebalance the tree? Which node was unbalanced?
Section 26.7
▼26.7.1
Why is the createNewNode method defined protected? When is it invoked?
▼26.7.2
When is the updateHeight method invoked? When is the balanceFactor method invoked? When is the balancePath method invoked? Will the program work if you replace the break in line 61 in the AVLTree class with return and add return at line 69?
▼26.7.3
What are data fields in the AVLTree class?
▼26.7.4
In the insert and delete methods, once you have performed a rotation to balance a node in the tree, is it possible that there are still unbalanced nodes?
Section 26.8
▼26.8.1
Show the change of an AVL tree when inserting 1, 2, 3, 4, 10, 9, 7, 5, 8, 6 into the tree, in this order.
▼26.8.2
For the tree built in the preceding question, show its change after 1, 2, 3, 4, 10, 9, 7, 5, 8, 6 are deleted from the tree in this order.
▼26.8.3
Can you traverse the elements in an AVL tree using a foreach loop?
Section 26.9
▼26.9.1
What is the maximum/minimum height for an AVL tree of 3 nodes, 5 nodes, and 7 nodes?
▼26.9.2
If an AVL tree has a height of 3, what maximum number of nodes can the tree have? What minimum number of nodes can the tree have?
▼26.9.3
If an AVL tree has a height of 4, what maximum number of nodes can the tree have? What minimum number of nodes can the tree have?