Note: In this homework set, log denotes the natural logarithm, i.e. the logarithm in base e. Following the notation used in the textbook, we write A[1..n] to mean an array A indexed from 1 to n. This means the first entry of A is A[1].

Question 1 (Heap). Illustrate all intermediate steps (as a sequence of binary trees) for the operation Insert(A,20) applied to the max heap A = [18,13,9,5,12,8,7,4,0,6].

Question 2 (Heap). The function Increase key(A,i,k) has the following pseudocode.

function Increase key(A,i,k)

Require: A[1..n] is a max heap.

Require: 1 i A.heap size is an index of A.

Require: k A[i] is a real number.

1: A[i] k

2: while i > 1 and A[parent(i)] < A[i]:

3: swap A[i] and A[parent(i)]

4: i parent(i)

Note that each swap operation on line 3 typically requires three assignments.

temp A[i]

A[i] A[parent(i)] A[parent(i)] temp

Show how the idea of the inner loop of Insertion Sort can be used to reduce these three assignments down to just one assignment, for this function Increase key(A,i,k).

Question 3 (Binary trees). The binary-search-tree property and the min-heap property are two properties that can describe binary trees.

• Can a binary tree with at least 3 nodes with distinct key values satisfy both properties?

Justify your answer.

• Let A be a min heap with n Is it possible to print out the keys of all n elements of A in sorted order in O(n) time? If this is possible, please show how. If this is not possible, explain why not. [4 points]
• Explain in detail why if a node in a binary search tree has two childern, then its successor has no left child and its predecessor has no right child. [4 points]

Question 4 (Binary search tree). (i) We can sort a given set of n numbers by first building a binary search tree containing these numbers (using tree-insert repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?

(ii) Describe a binary search tree with n nodes, such that the average depth of a node in the tree is (logn) but the height of the tree is (logn). Given an asymptotic upper bound on the height of a binary search tree with n nodes, in which the average depth of a node is (logn).

Question 5 (AVL Tree). Suppose that a,b,c,d,e,f,g,h are eight elements with the key values 38,22,33,25,47,30,28,31 respectively. Starting with an empty AVL tree (i.e. with no nodes), insert the elements a,b,c,d,e,f,g,h in this given order (where a is the first element to be inserted) into the AVL tree, and let T be the final AVL tree obtained after the insertion of all eight elements. Assume that for every insertion, the AVL tree remains as an AVL tree.

• Please draw T, and please also draw all seven intermediate AVL trees obtained in this sequence of insertions. [4 points]
• Let T₁ be the AVL tree obtained by deleting element g (which has key value 28) from T.

Please draw T₁, and please show all intermediate steps by drawing. (iii) Let T₂ be the AVL tree obtained by deleting element e (which has key value 47) from T. (Note that T still has element f.) Please draw T₂, and please show all intermediate steps by drawing.

Question 6 (BSTs and AVL trees). (i) The binary tree shown in Fig. 1 is a BST, but not an AVL tree. Explain why this BST is not an AVL tree, and perform the necessary rotations, so that it becomes an AVL tree. Please indicate clearly all rotation steps, including the node used for each rotation step. Please also draw all intermediate trees obtained in your sequence of rotations, as well as the final AVL tree. (Note that a rotation step is either Left Rotate(node) or Right Rotate(node). For simplicity, assume that the elements of this BST are labeled by their key values, e.g. node 22 has key 22, node

49 has key 49, etc.)

Figure 1: AVL Tree for Question 6(i)

(ii) Design an algorithm Tree Merge(T,T⁰), where the two inputs T,T⁰ are binary search trees, and where the output is a merged binary search tree consisting of all elements in T and T⁰, possibly with repeated key values. You may write your algorithm in pseudocode. Explain in as much detail as possible why the binary-search-tree property is still maintained after running your algorithm. What is the complexity of your algorithm? Justify your answer. Question 7 (Analysis of d-ary heaps). As mentioned in Lecture L0301 Slide 23, we define a d-ary heap (for d 2) analogously like a binary heap, but instead, in the d-ary tree visualization of a d-ary heap, we allow every node to have at most d children. In this question, you will extend several binary heap operations to the case of d-ary heaps. When asked to design an algorithm, you may write your algorithm in pseudocode.

• For a d-ary heap A, given to us in its array representation, describe and explain how its d-ary tree visualization can be obtained. Please give an example involving a 3-ary heap with 15 elements. [5 points]
• What is the height of a d-ary heap with n elements? Find an exact expression for this height in terms of n and d, and justify your answer with details. [5 points]

In Week 3, we introduced several heap operations, including Extract Max(A), Insert(A,x), and Increase Key(A,i,k), where A was assumed to be a binary max heap.

• Design an efficient algorithm that extends Extract Max(A) to d-ary max heaps A[1..n]. Your algorithm should return an element with the largest key and remove it from the input array A. (If there are multiple elements with the same largest key value, then returning any of these elements would be okay.) Analyze the running time of your algorithm in terms of d and n. [5 points]
• Design an efficient algorithm that extends Insert(A,x) to d-ary max heaps A[1..n], where x is an element to be inserted into A while still maintaining the d-ary max heap data structure. (Assume that x has a valid numerical key value key.) Analyze the running time of your algorithm in terms of d and n. [5 points]
• Design an efficient algorithm that extends Increase Key(A,i,k) to d-ary max heaps A[1..n]. Here, A is assumed to be a d-ary max heap, i is an index of A, and k is a value. Your algorithm should flag an error if k < A[i], but would otherwise set A[i] = k and then update the d-ary max heap data structure appropriately. Analyze the running time of your algorithm in terms of d and n. [5 points]