Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #6 -- Due Fri 09 July 1999 : 09.30am

Clarifications in response to student questions are posted in red typeface.

• Question 1. Given the sequence {-3, 8, 2, -1, 4, 6, -2, 10},
  (a) [1 point] Diagram an unbalanced binary search tree (BST) for this sequence. Right and left subtrees of the root should differ by two levels. This means that the balance factor can be -2 or +2.

  (b) [1 point] Traverse the BST using DFS and label the vertices by their values as they are encountered, as you did for Homework #5.

  (c) [1 point] Repeat Question 1b), but for BFS instead of DFS.

  (d) [1 point] Tell which method - DFS or BFS - would be better for outputting the BST values in sorted order. You do not have to start at the root of the tree. To get credit, you must explain your answer in 1-2 sentences.

• Question 2. Given the sequence S = {-9, 2, 4, 6, 30, -10, 1, 5, 8, 7},
  (a) [1 point] Diagram a binary search tree (BST) for this sequence.

  (b) [1 point] Insert the values -46, -47, 38, 39, 40, and 45 into the BST you diagrammed in Question 2a) and draw the new BST (the resultant tree, after all values are inserted).

  (c) [1 point] Using the array representation of a binary tree that we discussed in class, diagram the array representation of the tree you obtained in Question 2a).

  (d) [1 point] Repeat Question 2c) for the tree you obtained in Question 2b).

• Question 3. Given the sequence S = {-9, 2, 4, 6, 30, -10, 1, 5, 8, 7},
  (a) [2 points] Analyze the space requirement of the BSTs you produced in Questions 2a) and 2b) in terms of (i) number of levels L, and (ii) number of nodes in the BST, divided by the number of nodes in a full binary tree having L levels. Let us call the quotient in ii) the fill factor.

  (b) [1 point] Give a general algorithm and formula for computing the fill factor from an array representation of a BST that has N nonempty nodes and L levels.

  (c) [1 point] Apply the formula for fill factor that you derived in Question 3b) to yield the fill factor for the two trees you produced in Questions 2c) and 2d).

• Question 4. Repeat Question 1 for an AVL tree instead of a BST.

• Question 5. Given sequence S = {-9, 2, 4, 6, 30, -10, 1, 5, 8, 7} that we used previously,
  (a) [1 point] Diagram an AVL tree that stores S.

  (b) [3 points] Insert the values -46, -47, and 39 into the AVL tree you diagrammed in Question 5a), and draw all rotations for each insertion.

• Question 6. Make tabular work budgets for comparisons, incrementations, and memory I/O operations, with a Big-Oh complexity estimate, for:
  (a) [2 points] Each insertion involved in building the AVL tree in Question 5a). That is, you must show the budget for building the entire AVL tree. The i-th line of the budget must describe the work required to insert the i-th number in the input sequence.

  (b) [2 points] Each insertion in Question 5b).

Copyright © 1999 by Mark S. Schmalz.