Answer the following questions.
(1) Depict the binary search tree, in the same way as that shown in Fig. 1, constructed by inserting the keys prepared in a number list one by one from the first element. Note that once a key is inserted, it is not moved.
(2) Depict the binary search tree after deleting key 6 from the binary search tree shown in Fig. 1.
(3) Depict the binary search tree after re-inserting key 6 to the binary search tree made in (2).
(4) Given a list of different numbers, consider sorting the numbers in ascending order by first constructing a binary search tree from the list and then using a recursive function that traverses the nodes of it. Let us refer to this recursive function as traverse_tree(x) and a node of the tree as x. Answer the correct order of the calls to the following three functions inside traverse_tree(x) when x is not NIL. Note that x.left is the left child node and x.right is the right child node of x, and each of them becomes NIL when it does not exist.
traverse_tree(x.right)
traverse_tree(x.left)
print(x)
(5) Answer the best-case time complexity order and worst-case time complexity order of the sorting algorithm in (4) for a list of different numbers.
Assume that there are types of items, , and that the weight of each item is (). Note that is a positive integer and . Also assume that there are a sufficient number of items of each type. Answer the following questions. Note that the solutions must be given as equations that can be evaluated in constant time.
(1) denotes whether it is possible to make the total weight equal to a given non-negative integer , using at most one item of each type from to . If possible, , otherwise, . Express using some (for ) other than . You do not need to care about boundary conditions (i.e., you only need to consider the cases where ).
(2) denotes the minimum number of items required to make the total weight equal to a given non-negative integer , using as many items of each type from to as needed. Express using some (for ) other than . As in (1), you do not need to care about boundary conditions.
(3) denotes the number of ways to make the total weight equal to a given nonnegative integer , using as many items of each type from to as needed. Express using some (for ) other than . Note that there is no distinction between items of the same type. As in (1), you do not need to care about boundary conditions.
