[SOLVED] data structure algorithm CSC263H1, Fall 2019 Problem Set 3 Sample Solutions

CSC263H1, Fall 2019 Problem Set 3 Sample Solutions
CSC263H1: Problem Set 3 Sample Solutions
Due Tuesday October 8 before 10pm
Note: solutions may be incomplete, and meant to be used as guidelines only. We encourage you to ask follow-up questions on the course forum or during office hours.
1. [6 marks] Idealy-Balanced vs Height-Balanced Trees
(a) [6 marks] Draw a minimal (smallest possible) example of a height-balanced tree that is not ideally- balanced. To receive (any) credit, you must write the balance factor next to every node, and also clearly indicate why the tree is not ideally balanced. Full points given for a minimal example.
Solution
o BF = -1 /
/
BF = -1 o o BF = -1 <— node lacks two children, / /not ideally balanced!BF = -1 o o o BF = 0// BF=0o BF = 0 Page allowance: Please neatly present your solution using a single page. Any additional pages will not be marked.2. [4 marks] AVL Operations(a) [1 mark] Let T be an empty AVL tree. Consider inserting these keys using the AVL insertionalgorithm, in this order: 3, 1, 4, 15, 9. Draw the resulting tree. Do not draw the intermediate trees.Solution 3 / / 19/4 15 (b) [1 mark] Indicate whether any rotations were required, and, if so, how many of each kind.(c) [1 mark] Next, delete the key 1 using the AVL deletion algorithm. Draw the resulting tree. Do not draw the intermediate trees.SolutionOne double-right-left-rotation was needed. No other rotations.Page 1/4CSC263H1, Fall 2019 Problem Set 3 Sample Solutions Solution 9 / /3 15 4 (d) [1 mark] Indicate whether any rotations were required, and, if so, how many of each kind.Page allowance: Please neatly present your solution using a single page. Any additional pages will not be marked.SolutionOne left rotation was needed. No other rotations.Page 2/4CSC263H1, Fall 2019 Problem Set 3 Sample Solutions 3. [10 marks] Augmentation. Assume that T is a balanced binary search tree data structure (AVL tree). Explain how to augment T to support the operation FindAverage(T) which finds (in constant time) the average of the keys stored in the subtree rooted at T, while preserving the worst-case running time of the operations Rotation, BSTInsert and BSTDelete.(a) [3 marks] Briefly explain what additional information needs to be stored, and where it will be stored.(b) [4 marks] Justify that the operations BSTInsert, and BSTDelete can be modified to maintain the newly stored information from part (a) while preserving their worst-case running time. You may explain this with a brief logical argument including references to theorems in the textbook; alternatively, you may present pseudocode.SolutionWe augment each node x in the tree with the following information: x.size = the number of nodes stored in the subtree rooted at x, and x.sum = the sum of the keys stored in the subtree rooted at x.Note that other augmentations may be used.SolutionThe following solution follows from the proof of Theorem 14.1 from the textbook. Assuming the left and right children of a node x are properly augmented, the size and sum attributes of x can be computed by x.size = x.left.size + x.right.size + 1 x.sum = x.left.sum + x.right.sum + x.key.(1)For simplicity, we let Nil.size = 0 and Nil.sum = 0.The AVL Insert(x) operation can be modified as follows. Consider the tree after x is inserted, but before rotations occur. The only nodes whose subtrees change as a result of inserting x are those along the path from x to the root. Using Equation (1), we can update the size and sum attributes of each node from x up to the root. This takes procedure takes O(log n) additional time. Finally, we can proceed with the standard balancing procedure. When a rotation occurs, we must update the attributes of all nodes involved in the rotation whose subtrees change. There are a constant number of such nodes after each rotation. Since at most 1 rotation is performed in AVL insertion, performing these updates takes O(1) additional time. The worst-case running time of Insert(x) is still O(logn).The AVL Delete(x) operation can be modified similarly. Recall that deletion from AVL trees reduces to removing a leaf node z. Immediately after z is removed but before rotations occur, update the attributes of all nodes from zs parent up to the root. Additionally, update the attributes of nodes involved in rotations. Note that unlike insertions, O(logn) rotations may occur during deletions. Since the overhead added to a single rotation is O(1), the worst-case running time of Delete(x) is still O(log n). (c) [3 marks] Write pseudocode for the operation FindAverage(T).SolutionFindAverage(T):return T.sum / T.size Page 3/4CSC263H1, Fall 2019 Problem Set 3 Sample SolutionsThe worst-case running time of FindAverage(T) is (1), as required.Page allowance: Please neatly present your solution using one or two pages. Any additional pages will not be marked. To save space, do not re-describe or copy/paste pseudocode for standard AVL tree operations, unless your pseudocode is explicitly modifying those operations. Page 4/4