Suppose we want to design a binary decision tree of comparisons that can determi
ID: 3848430 • Letter: S
Question
Suppose we want to design a binary decision tree of comparisons that can determine the sorted order of any input list of 4 distinct positive integers a_1, a_2, a_3, a_4 in that order. For example, the input might be a_1 = 7, a_2 = 3, a_3 = 6, a_4 = 5. So, the first integer is denoted a_1, and so on. At each node in the tree, we compare the values of two specific entries a_i, a_j in the list, then descend to a child node according to the result of the comparison at the parent node. Each leaf should correspond to a specific sorted order of the entries, for example a_3 a_1 a_2 a_4. a. How many leaves should the binary tree have, in order to accommodate all possible sorted orders? Explain in terms of this specific example with 4 input items. b. What must be the height of the binary tree in order to provide enough leaves? Explain in terms of this specific example with 4 input items. c. Is the height you gave above in b. a lower bound or an upper bound for the height of any binary decision tree you might design to determine the sorted order of the 4 input items? d. Using asymptotic notation, what must the height, h, of the tree be in order to sort n items? Prove it. You may assume the general case corresponding to parts a. and b. are true.Explanation / Answer
a. As the input sequence of numbers can be in any order, leaves of the tree must accommodate all possible permutations of the input sequence. Hence required no. of leaves = 4! = 24.
Explanation : Let us consider the first element in the sorted order. It can be anything out of a1, a2, a3 or a4. Hence, we have 4 possibilities for first element. For second element, we would have 3 possibilities, as we would already have used one element as the first element. So, for every first element that we take (out of 4), we have 3 possibilities for second element. Hence, total possibilities = (4 x 3) for our sequence of first and second elements. Nebxt, for third element we will have two choices, and upon selection of one, for the last element we will have only 1 element to choose from.
Hence, total possibilities = (4 x 3 x 2 x 1) = 24.
As the tree must be able to output any sequence out of these 24, it must contain exactly 24 leaves.
b. Required height of the tree would be 7.
In the worst case, elements would already be in sorted or reverse-sorted order. In that case, we will need three comparisons of a1 (with a2, a3, and a4) to establish that it is the first element in sorted order. Next, we will require two comparisons for a2, and then one comparison for a3. So there are a total of 6 internal nodes and one leaf node containing the order of elements, hence height of the tree would be 7.
Please note that a complate binary tree of height 7 could have had 64 leaves (2^(7-1)), but in this case we will not end up with a complete binary tree. As such, only in the worst case we will need these many internal nodes for comparison. In other cases, we will be able to predict earlier.
c. Clearly, it is a lower bound.
We can build other trees too which would do the same task. We definitely need at least these many comparisons for sorting, so it is a lower bound.
d. h = O(n^2)
Contrary to the general case of O(log(N)) height of a tree with N nodes, here the height will be different, owing to the fact that we will need more number of comparisons in the worst case.
Suppose there are n numbers. The maximum number of comparisons required will be, for the worst case, n*(n-1)/2.
Hence, height of the tree will also be n*(n-1)/2.
In asymptotic notation, it is O(n(n-1)/2) = O(n^2/2 - n/2) = O(n^2)