Questions 4.1 to 4.3 refer to the tree in Figure 4.70.
4.1 For the tree in Figure 4.70:
a. Which node is the root?
b. Which nodes are leaves? Get solution
4.2 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. Get solution
4.3 What is the depth of the tree in Figure 4.70?
Sol: 4.
4.4 Show that in a binary tree of N nodes, there are N + 1 null links representing children. Get solution
4.8 Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 4.71. Get solution
4.9 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. Get solution
4.10 Write a program that lists all files in a directory and their sizes. Mimic the routine in the online code. Get solution
4.11 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. Get solution
4.13 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. Get solution
4.14 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 alreadyin 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? Get solution
4.18 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? Get solution
4.19 Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree. Get solution
4.21 Write the remaining procedures to implement AVL single and double rotations. Get solution
4.24 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. - Get solution
4.25 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? Get solution
4.26 Write the methods to perform the double rotation without the inefficiency of doing two single rotations. Get solution
4.27 Show the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in Figure 4.72. Get solution
4.28 Show the result of deleting the element with key 6 in the resulting splay tree for the
previous exercise. Get solution
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. Get solution
4.31 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? Get solution
4.32 Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node. Get solution
4.33 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. Get solution
4.34 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? Get solution
4.35 Write a method to generate the AVL tree of height h with fewest nodes. What is the running time of your method? Get solution
4.37 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. Get solution
4.38 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 X’s left subtree appear to the left of X and all elements in X’s right subtree appear to the right of X. Get solution
4.44 Show how the tree in Figure 4.73 is represented using a child/sibling link implementation. Get solution
4.46 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? Get solution
4.48 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. Get solution
4.49 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. Get solution
4.50 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? Sol: You need an extra bit for each thread.
c. What is the advantage of using threaded trees? Sol: You can do tree traversals somewhat easier and without recursion. The disadvantage is that it reeks of old-style hacking.
IX: {Series |(} {2}
IX: {Series!geometric|(} {4}
IX: {Euler’s constant} {4}
IX: {Series!geometric|)} {4}
IX: {Series!arithmetic|(} {4}
IX: {Series!arithmetic|)} {5}
IX: {Series!harmonic|(} {5}
IX: {Euler’s constant} {5}
IX: {Series!harmonic|)} {5}
IX: {Series|)} {5} Get solution
