Chapter 12 Answers

Overview

Question 12.1

1. Are each of the trees binary? Yes
2. Are each in sorted order? Infix traversal, d is descending; c, e, f, g, h are ascending. What does that mean? For infix, the tree nodes are arranged so that left child nodes have values no greater (less for descending) and right child nodes have values no less (greater for descending) than the parent.
3. What is the height of (d)? 4 (e)? 2
4. For full binary trees, decision trees, and heaps we could make and prove general claims that the height h of a binary tree is related to the number of nodes. Why was that useful? Determines the complexity of algorithm, often O(lg₂ n) for n node binary tree.
5. What are some of the relationships between the height of an arbitrary binary tree such as those above and the number of nodes?

   A few:

   1. For height h there are at least h+1 nodes.
   2. For height h there are at most 2^h+1-1 nodes (see g).
   3. For n nodes the height is at least ëlg nû (see h).

 

Binary search trees

Question 12.2

• Can the minimum and maximum be found in the tree at right in O(h) time? Yes
• Can the minimum and maximum be found in the heap at right in O(h) time? Maximum but no minimum.
• Can a hash table efficiently support all the above operations?
  • search on a key value  Yes
  • dynamic insertions and deletions  Yes, deletions efficient for doubly linked
  • updates of satellite data associated with a key value Yes
  • locating predecessors and successors to a particular key value No
  • maintain data in sorted order No
  • locate minimum and maximum No
• Can a sorted array efficiently support all the above operations?
  • search on a key value. Yes, binary search
  • dynamic insertions and deletions. O(n)
  • updates of satellite data associated with a key value. Yes - assumes array holds keys.
  • locating predecessors and successors to a particular key value. Yes.
  • maintain data in sorted order. O(n) for insert
  • locate minimum and maximum. Efficient for keys but O(n) for data.

Question 12.3 - Does the tree at right satisfy the binary-search-tree property? Yes

Question 12.4

1. Diagram the tree constructed by root.Insert().

   Node root = new Node( 4, null, null, null);                 4
              root.Insert( 3 );                                           /   \
              root.Insert( 1 );                                         3      6
              root.Insert( 2 );                                       /        / 
              root.Insert( 6 );                                      1       5
              root.Insert( 5 );                                        \
                                                                               2
                             

2. Where in the code is the parent node p assigned?      this.p = p;
3. From the trees (a) and (b) below:

   What is printed by root.Inorder()? 2 3 5 5 7 8

   What is the best case for Insert(6)? a. Worse case for (a) is the tree height, for (b) occurs for key £ 2.

   What is the worse case for Insert(6)? b. For (a) is the tree height, for (b) occurs for  3 £  key £  7.
    

4. What is the complexity of Inorder()?   

   Our eyeballs tell us that each node must always be visited one time so T(n) = Q(n) for full tree.

   Assuming a full tree, the recurrence is:

   2T(n/2) + Q(1)

   By Case 1 of the Master Theorem:

   n^log2² = n¹

   f(n) = Q(1) = 1 = n⁰ = n^1-e for e=1

   T(n) = Q(n^log2²)= Q(n)

    

Question 12.5

• Do both of the above trees satisfy the binary-search-tree property? Yes
• What is the implication of having non-unique keys? Must define some heuristic to determine which node to associate with key (e.g. return on a search or to delete).

 

Inorder Traversal

Question 12.6

1. Are c and d > 0?     Yes
2. Can we pick any b₁ as long as we satisfy 0 ≤ b₁ ≤ 2c + d? Yes
3. Does picking 0 ≤ b₁ ≤ 2c + d satisfy the relation?    Yes
4. Have we proven T(n) = Q(n)?                                  Yes
5. Give the pre, post and in-order traversal of the tree at right.

   Pre - 15, 6, 2 2, 4, 7, 13, 9, 18, 17, 20

   Post - 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15

   In-order - 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20

    

6. What is the maximum memory use for the tree (number of activation records) during in-order traversal? 5
7. Is it better, worse or the same for pre and post order? About the same since all methods are essentially depth-first.
8. What is the upper-bound of memory use of in-order traversal? O(h)

Search

Question 12.7

1. What are the preconditions? $x such that x=NIL or x.key=k postconditions? result = x such that x=NIL or x.key=k
2. Keep track of the activation records while tracing the nodes searched for 9. 15, 6, 7, 13, 9.     For 8. 15, 6, 7, 13, 9
3. Does the tree need to be balanced?  No

   Balanced binary trees (AVL) subtrees of every node never differ in height by more than one. The tree above is not balanced because the left subtree of node 15 has height 4 and the right height 2.

4. What is the number of activation records required for the trees below? (a) 3  (b) 5
5. What is the tree height?  (a) 2  (b) 4
6. What is an upper-bound performance in terms of height? O(h)
7. What is a lower-bound? W(lg n)
8. Can you as easily state a reasonably accurate average performance for an arbitrary search tree? No. However, the expected height of a randomly built binary search tree on n keys is O(lg n). The text discusses in section 12.4.
9. Which of the following have the better search performance and why? (a) because lower height implies shorter search. What was the approximate order that data was inserted into each? (a) 4, 2, 3, 7, 6    (b) 2, 3, 4, 7, 6

(a)                  4                     /    \                   2       7                    \      /                      3  6

(b)     2           \            3              \               4                 \                  7                 /               6

Convert Tail Recursive operation to an Iterative Operation

Question 12.8.1

Is the following tail-recursive? No

void Inorder_Tree_Walk ( Node x)     if x ¹ NIL         Inorder_Tree_Walk ( x.left )         print x.key         Inorder_Tree_Walk ( x.right )

Question 12.8.2

1. Trace below tree using iterative search, the nodes searched for 9. 15, 6, 7, 13, 9.     For 8. 15, 6, 7, 13, 9
2. What is the best case for size n? W(lg n)
3. What is the worst case for size n? O(h)
4. What is to be gained by this conversion? Activation records, use is 1.
5. If the tree is full, én/2ù nodes at bottom, can we state a tighter upper-bound performance in terms of n? O(lg n)

Successor

Question 12.9

1. What is the successor of 7, 15, 13, 20? 9, 17, 15, NIL
2. Trace Tree_Minimum starting at 15. 15, 6, 3, 2. Starting at 7. 7
3. What is the predecessor of 7, 15, 9, 2? 6, 13, 7, NIL
4. What does y ¬ x.p do at x=4?  y ¬ 4.p ¬ 3
5. *Trace Tree_Successor starting at 15, 7, and 13.
6. What is the precondition for Tree_minimum?   x ¹ NIL
7. Convert Tree_Minimum to a tail-recursive algorithm.

   Node Tree_Minimum (preserves Node x)     if x.left = NIL         return x     return  Tree_Minimum ( x.left )

8. Give Tree_Maximum.

   Node Tree_Maximum (preserves Node x)     if x.right = NIL         return x     return  Tree_Maximum ( x.right )

9. Give a tail-recursive Tree_Successor.

Insertion and Deletion

Question 12.10

1. Trace inserting 13, 8, 11, 2, 5.

   8 (left child of 9)

   11 (right child of 9)

   2 (right child of 2)

   5 (left child of 9)

    

2. What happened in the attempt to insert a key that was already in the tree? Placed in right subtree of the matching key.
3. Do insertions occur at internal nodes? No
4. What is the worst-case number of key comparisons for the tree at right after inserting 13? Give an example. 4, inserting 12-17.
5. What is the best case? In what cases? 3, inserting key<12 or key>17.
6. Insert 2, 3, 4, 5, 6, 7 into a binary search tree. Give two different trees and the search upper-bound of each.     

   2           \            3              \               4                 \                  7                 /               6  height = 4 = O(h)

   4                /    \              2       7               \      /                3  6        height = 2 = O(h) = O(lg n)

Question 12.11 - From Figure (a)

1. Trace deleting 7.
2. Trace deleting 10. 
3. Trace deleting 15.

Question

• Give an algorithm to count the number of nodes in a binary tree. What is the order of the algorithm? O(n)
• Give an algorithm to count the number of leaf nodes in a tree. What is the order of the algorithm? O(n)
• Give an algorithm to determine the height of a tree. What is the order of the algorithm? O(n)