References 167IX: {Series

For the tree in Figure 4.70: a. Which node is the root? b. Which nodes are leaves?

For each node in the tree of Figure 4.70: a. Name the parent node. b. List the children. c. List the siblings. d. Compute the depth. e. Compute the height.

What is the depth of the tree in Figure 4.70?

Show that in a binary tree of N nodes, there are N + 1 null links representing children.

Show that the maximum number of nodes in a binary tree of height h is 2h+1 1.

A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.

Suppose a binary tree has leaves l1, l2, ... , lM at depths d1, d2, ... , dM, respectively. Prove that M i=1 2di 1 and determine when the equality is true.

Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 4.71.

a. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree. b. Show the result of deleting the root.

Write a program that lists all files in a directory and their sizes. Mimic the routine in the online code.

Write an implementation of the TreeSet class, with associated iterators using a binary search tree. Add to each node a link to the parent node.

Write an implementation of the TreeMap class by storing a data member of type TreeSet<Map.Entry<KeyType,ValueType>>.

Write an implementation of the TreeSet class, with associated iterators, using a binary search tree. Add to each node a link to the next smallest and next largest node. To make your code simpler, add a header and tail node which are not part of the binary search tree, but help make the linked list part of the code simpler.

Suppose you want to perform an experiment to verify the problems that can be caused by random insert/remove pairs. Here is a strategy that is not perfectly random, but close enough. You build a tree with N elements by inserting N elements chosen at random from the range 1 to M = N. You then perform N2 pairs of insertions followed by deletions. Assume the existence of a routine, randomInteger(a, b), which returns a uniform random integer between a and b inclusive. a. Explain how to generate a random integer between 1 and M that is not already in the tree (so a random insertion can be performed). In terms of N and , what is the running time of this operation? b. Explain how to generate a random integer between 1 and M that is already in the tree (so a random deletion can be performed). What is the running time of this operation? c. What is a good choice of ? Why?

Write a program to evaluate empirically the following strategies for removing nodes with two children: a. Replace with the largest node, X, in TL and recursively remove X. b. Alternately replace with the largest node in TL and the smallest node in TR, and recursively remove the appropriate node. c. Replace with either the largest node in TL or the smallest node in TR (recursively removing the appropriate node), making the choice randomly. Which strategy seems to give the most balance? Which takes the least CPU time to process the entire sequence?

Redo the binary search tree class to implement lazy deletion. Note carefully that this affects all of the routines. Especially challenging are findMin and findMax, which must now be done recursively.

Prove that the depth of a random binary search tree (depth of the deepest node) is O(logN), on average.

a. Give a precise expression for the minimum number of nodes in an AVL tree of height h. b. What is the minimum number of nodes in an AVL tree of height 15?

Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.

Keys 1, 2, ... , 2k 1 are inserted in order into an initially empty AVL tree. Prove that the resulting tree is perfectly balanced.

Write the remaining procedures to implement AVL single and double rotations

Design a linear-time algorithm that verifies that the height information in an AVL tree is correctly maintained and that the balance property is in order.

Write a nonrecursive method to insert into an AVL tree.

Show that the deletion algorithm in Figure 4.44 is correct, and explain what happens if > is used instead of >= at lines 32 and 38 in Figure 4.39.

a. How many bits are required per node to store the height of a node in an N-node AVL tree? b. What is the smallest AVL tree that overflows an 8-bit height counter?

Write the methods to perform the double rotation without the inefficiency of doing two single rotations.

Show the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in Figure 4.72.

Show the result of deleting the element with key 6 in the resulting splay tree for the previous exercise

a. Show that if all nodes in a splay tree are accessed in sequential order, the resulting tree consists of a chain of left children.b. Show that if all nodes in a splay tree are accessed in sequential order, then the total access time is O(N), regardless of the initial tree.

Write a program to perform random operations on splay trees. Count the total number of rotations performed over the sequence. How does the running time compare to AVL trees and unbalanced binary search trees?

Write efficient methods that take only a reference to the root of a binary tree, T, and compute: a. The number of nodes in T. b. The number of leaves in T. c. The number of full nodes in T. What is the running time of your routines?

Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node

Write a recursive method that takes a reference to the root node of a tree T and returns a reference to the root node of the tree that results from removing all leaves from T

Write a method to generate an N-node random binary search tree with distinct keys 1 through N. What is the running time of your routine?

Write a method to generate the AVL tree of height h with fewest nodes. What is the running time of your method?

Write a method to generate a perfectly balanced binary search tree of height h with keys 1 through 2h+1 1. What is the running time of your method?

Write a method that takes as input a binary search tree, T, and two keys k1 and k2, which are ordered so that k1 k2, and prints all elements X in the tree such that k1 Key(X) k2. Do not assume any information about the type of keys except that they can be ordered (consistently). Your program should run in O(K + logN) average time, where K is the number of keys printed. Bound the running time of your algorithm.

The larger binary trees in this chapter were generated automatically by a program. This was done by assigning an (x, y) coordinate to each tree node, drawing a circle around each coordinate (this is hard to see in some pictures), and connecting each node to its parent. Assume you have a binary search tree stored in memory (perhaps generated by one of the routines above) and that each node has two extra fields to store the coordinates. a. The x coordinate can be computed by assigning the inorder traversal number. Write a routine to do this for each node in the tree. b. The y coordinate can be computed by using the negative of the depth of the node. Write a routine to do this for each node in the tree. c. In terms of some imaginary unit, what will the dimensions of the picture be? How can you adjust the units so that the tree is always roughly two-thirds as high as it is wide?d. Prove that using this system no lines cross, and that for any node, X, all elements in Xs left subtree appear to the left of X and all elements in Xs right subtree appear to the right of X.

Write a general-purpose tree-drawing program that will convert a tree into the following graph-assembler instructions: a. Circle(X, Y) b. DrawLine(i, j) The first instruction draws a circle at (X, Y), and the second instruction connects the ith circle to the jth circle (circles are numbered in the order drawn). You should either make this a program and define some sort of input language or make this a method that can be called from any program. What is the running time of your routine?

(This exercise assumes familiarity with the Java Swing Library.) Write a program that reads graph-assembler instructions and generates Java code that draws into a canvas. (Note that you have to scale the stored coordinates into pixels.)

Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You must do this in linear time. Prove your time bound.

a. Write a routine to perform insertion into a B-tree. b. Write a routine to perform deletion from a B-tree. When an item is deleted, is it necessary to update information in the internal nodes? c. Modify your insertion routine so that if an attempt is made to add into a node that already has M entries, a search is performed for a sibling with less than M children before the node is split.

A B-tree of order M is a B-tree in which each interior node has between 2M/3 and M children. Describe a method to perform insertion into a B-tree

Show how the tree in Figure 4.73 is represented using a child/sibling link implementation

Write a procedure to traverse a tree stored with child/sibling links.

Two binary trees are similar if they are both empty or both nonempty and have similar left and right subtrees. Write a method to decide whether two binary trees are similar. What is the running time of your method?

Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 4.74 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. a. Give a polynomial time algorithm to decide if two trees are isomorphic. b. What is the running time of your program (there is a linear solution)?

a. Show that via AVL single rotations, any binary search tree T1 can be transformed into another search tree T2 (with the same items). b. Give an algorithm to perform this transformation using O(N logN) rotations on average. c. Show that this transformation can be done with O(N) rotations, worst case.

Suppose we want to add the operation findKth to our repertoire. The operation findKth(k) returns the kth smallest item in the tree. Assume all items are distinct. Explain how to modify the binary search tree to support this operation in O(logN) average time, without sacrificing the time bounds of any other operation.

Since a binary search tree with N nodes has N + 1 null references, half the space allocated in a binary search tree for link information is wasted. Suppose that if a node has a null left child, we make its left child link to its inorder predecessor, and if a node has a null right child, we make its right child link to its inorder successor. This is known as a threaded tree, and the extra links are called threads. a. How can we distinguish threads from real children links? b. Write routines to perform insertion and deletion into a tree threaded in the manner described above. c. What is the advantage of using threaded trees?

References 167 IX: {Series |(} {2} IX: {Series!geometric|(} {4} IX: {Eulers constant} {4} IX: {Series!geometric|)} {4} IX: {Series!arithmetic|(} {4} IX: {Series!arithmetic|)} {5} IX: {Series!harmonic|(} {5} IX: {Eulers constant} {5} IX: {Series!harmonic|)} {5} IX: {Series|)} {5} Figure 4.75 Sample input for Exercise 4.53 Eulers constant: 4, 5 Series: 2-5 arithmetic: 4-5 geometric: 4 harmonic: 5 Figure 4.76 Sample output for Exercise 4.53 c. Show (by induction) that f(N) = (N 2)/3 is a solution to the equation in part (b), with the initial conditions in part (a). d. Use the results of Exercise 4.6 to determine the average number of leaves in an N node binary search tree

Write a program that reads a Java source code file and outputs a list of all identifiers (that is, variable names but not keywords, not found in comments or string constants) in alphabetical order. Each identifier should be output with a list of line numbers on which it occurs.

Generate an index for a book. The input file consists of a set of index entries. Each line consists of the string IX:, followed by an index entry name enclosed in braces, followed by a page number that is enclosed in braces. Each ! in an index entry name represents a sub-level. A (|represents the start of a range, and a |) represents the end of the range. Occasionally, this range will be the same page. In that case, output only a single page number. Otherwise, do not collapse or expand ranges on your own. As an example, Figure 4.75 shows sample input, and Figure 4.76 shows the corresponding output.