10.1 a. Show the effect of making the following insertions into an initially empty binary search tree:
30, 40, 20, 90, 10, 50, 70, 60, 80
b. Find a different ordering of the above elements whose insertions would generate the same binary search
tree as in part a. Get the solution of 10.1
10.2 Describe in English how to remove each of the following from a binary search tree:
a. an element with no children
b. an element with one child
c. an element with two children Get the solution of 10.2
10.3 a. For any positive integer n, describe how to arrange the integers 1,2, . . . , n so that when they are inserted into a BinarySearchTree object, the height of the tree will be linear in n.
b. For any positive integer n, describe how to arrange the integers 1,2, . . . , n so that when they are inserted into a BinarySearchTree object, the height of the tree will be logarithmic in n.
c. For any positive integer n, describe how to arrange the integers 1,2, . . . , n so that when they are inserted into an AVLTree object, the height of the tree will be logarithmic in n.
d. For any positive integer n, is it possible to arrange the integers 1,2, . . . , n so that when they are inserted into an AVLTree object, the height of the tree will be linear in n? Explain. Get the solution of 10.3
10.4 In each of the following binary search trees, perform a left rotation around 50.
a. Calculate max3.
b. Determine the formula for maxh for any h ≥ 0.
Hint: Use the Binary Tree Theorem from Chapter 9.
c. What is the maximum height of an AVL tree with 100 elements? Get the solution of 10.9
10.10 Show that the height of an AVL tree with 32 elements must be exactly 5.
Hint: calculate max4 (see Concept Exercise 10.9) and min6. Get the solution of 10.10
10.11 For the contains method in the BinarySearchTree class, worstTime(n) is linear in n. The AVLTree class does not override that method, but for the contains method in the AVLTree class, worstTime(n) is logarithmic in n. Explain. Get the solution of 10.11
10.12 The following program generates a BinarySearchTree object of n elements. Draw the tree when
n = 13. For any n ≥ 0, provide a ! (that is, Big Theta) estimate of height(n), that is, the height of the
BinarySearchTree object as a function of n.
import java.util.*;
public class weirdBST
{
public static void main (String[] args)
{
new weirdBST().run();
} // method main
public void run()
{
BinarySearchTree<Double> tree = new BinarySearchTree<Double>();
LinkedList<Double> list =new LinkedList<Double>();
System.out.println ("Enter n > 0");
int n = new Scanner (System.in).nextInt();
tree.add (1.0);
list.add (1.0);
int k = 2;
while (tree.size() < n)
addLevel (tree, n, k++, list);
System.out.println (tree.height());
} // method run
public void addLevel (BinarySearchTree<Double> tree, int n, int k,
LinkedList<Double> list)
{
final double SMALL = 0.00000000001;
LinkedList<Double> newList = new LinkedList<Double>();
Iterator<Double> itr = list.iterator();
double d = itr.next();
tree.add (d - 1.0);
newList.add (d - 1.0);
for (int i = 0; i < k && tree.size() < n; i++)
{
tree.add (d + SMALL );
newList.add (d + SMALL);
if (itr.hasNext())
d = itr.next();
} // for
list.clear();
list.addAll (newList);
} // method addLevel
} // class weirdBST Get the solution of 10.12
PROGRAMMING EXERCISES
10.1 In the BinarySearchTree class, test and develop a leaves method. Here is the method specification:
/**
* Returns the number of leaves in this BinarySearchTree object.
* The worstTime(n) is O(n).
*
* @return – the number of leaves in this BinarySearchTree object.
*
*/
public int leaves()
Test your method by adding tests to the BinarySearchTreeTest class available from the book’s website.
Hint: A recursive version, invoked by a wrapper method, can mimic the definition of leaves(t) from Section 9.1. Or, you can also develop an iterative version by creating a new iterator class in which the next method increments a count for each Entry object whose left and right fields are null. Get the solution of 10.1
10.2 Modify the BinarySearchTree class so that the iterators are fail-fast (see Appendix 1 for details on fail-fast iterators). Test your class by adding tests to the BinarySearchTreeTest class available from
the book’s website. Get the solution of 10.2
10.3 Modify the BinarySearchTree class so that BinarySearchTree objects are serializable (see
Appendix 1 for details on serializability). Test your class by adding tests to the BinarySearchTreeTest
class available from the book’s website. Get the solution of 10.3
10.4 Create a recursive version of the add method.
Hint: Make the add method a wrapper for a recursive method. Test your version with the relevant tests in the BinarySearchTreeTest class available from the book’s website. Get the solution of 10.4
10.5 In the BinarySearchTree class, modify the getEntry method so that it is a wrapper for a recursive
method. Test your version with the relevant tests in the BinarySearchTreeTest class available from
the book’s website. Get the solution of 10.5
10.6 (This exercise assumes you have completed Programming Projects 10.3 and 10.4.) Create a test suite for the AVLTree class.
Hint: Make very minor modifications to the BinarySearchTreeTest class available from the book’s
website. Use your test suite to increase your confidence in the correctness of the methods you defined in Programming Projects 10.3 and 10.4.
10.7 (This exercise assumes you have completed Programming Projects 10.3 and 10.4.) In the AVLTree class,
test and define the following method:
/**
* The height of this AVLTree object has been returned.
* The worstTime(n) is O(log n).
*
* @return the height of this AVLTree object.
*
*/
public int height()
Hint: Use the balanceFactor field in the AVLEntry class to guide you down the tree. Test your method
by adding tests to the BinarySearchTreeTest class available from the book’s website. Get the solution of 10.6
