Prove that a binary tree having n ≥ 1 real nodes has n + 1 external nodes
computer science
Description
Part 1: BST
Exercise 1. Prove that a binary tree having n ≥ 1 real nodes has n + 1 external nodes. (Hint: use induction)
Exercise 2. for a key k that is not found in binary search tree T, prove that both the greatest key less than k and the least key greater than lies on the path traced by the search fork.
Part 2: RBST
Exercise 3. Design and implement the permute(a) method that takes as input an array, a, that contains n distinct values and randomly permutes a. The method should run in O(n) time and you should prove that each of the n! possible permutations of a is equally probable.
Part 3: Red-Blak and 2-4
Exercise 4. Illustrate the 2-4 tree that corresponds to the Red-Black Tree illustrated in the additional file of this assignment.
Exercise 5. Consider the set of keys K = {1,2,3,4,5,6,7,8,9,10,11,12,
Draw a (2,4) tree storing K as its keys using the fewest number of nodes.
Exercise 6. Let T and U be (2,4) trees storing n and m entries, respectively, such that all the entries in T have keys less than the keys of all the entries in U. Describe an O(logn+logm)-time method for joining T and U into a single tree that stores all the entries in T and U. ( Hint: Find the right place to “splice” one tree into the other to maintain the (2,4) tree property)
Part 4. Heap
Exercise 7. A d-ary tree is a generalization of a binary tree in which each internal node has d children. Using Eytzinger’s method it is also possible to represent completed-ary trees using arrays. Work out the equations that, given index i, determine the index of i’s parent and each of i’s d children in this representation.
Exercise 8. Explain how the k largest elements from an unordered collection of size n can be
found in time O(nlogk) using O(k)
------------------------------
The solution of each part must be included in a separate directory named “Part” followed by the exercise number. Thus, the directories names are: Part1, Part2, Part3 and Part4.
