关于AVL Tree的Data Structure作业，五个分析问答题。
Question 1
In this question, you must use the insertion and deletion algorithms as described in the “Balanced Search Trees: AVL trees” handout posted on the course web site.
a. Insert keys 17, 7, 8, 14, 19, 6, 10, 21, 15, 12, 9, 11 (in this order) into an initially empty AVL tree, and show the resulting AVL tree T , including the balance factor of each node.
b. Delete key 17 from the above AVL tree T , and show the resulting AVL tree, including the balance factor of each node.
In each of the above questions, only the final tree should be shown: intermediate trees will be disregarded, and not given partial credit.
Question 2
In this question, you must use the insertion and deletion algorithms described in the “Balanced Search Trees: AVL trees” handout posted on the course web site.
a. Prove or disprove: “For any AVL tree T and any key x in T , if we let T1 = Delete(T, x) and T2 = Insert(T1, x), then T2 = T1 .” State clearly whether you are attempting to prove or disprove the statement. If proving, give a clear general argument; if disproving, give a concrete example where you show clearly each tree T, T1, T2 with the balance factors indicated beside each node.
b. Find an AVL tree T and a key x in T such that calling Delete(T, x) causes two rebalancing operations to take place. Your tree T should be as small as possible, in terms of the number of nodes, so that this takes place (you do not have to prove that it is indeed the smallest). Show your original tree T and the key x, then show the result of each rebalancing operation. Make sure to clearly indicate the balance factor next to each node.
Question 3
Give a simple, linear-time algorithm that determines if a Binary Search Tree (BST) satisfies the AVL balancing condition. The algorithm’s input is a pointer to the root of a BST T where each node u has the following fields: an integer key, and lchild and rchild which are pointers to the left and right children of u in T (if u has no left or right child, then u.lchild = Nil or u.rchild = Nil, respectively). There is no balance factor or height information already stored in any node. The algorithm’s output is True if T satisfies the AVL balancing condition, and False otherwise.
The worst-case running time of your algorithm must be O(n) where n is the number of nodes in T.
Describe your algorithm by giving its pseudo-code, and explain why its worst-case running time is O(n).
Question 4
We want an efficient algorithm for the following problem. The algorithm is given an integer m > 1, and then a (possibly infinite) sequence of distinct keys are input to the algorithm, one at a time. A query operation can occur at any point between any two key inputs in the sequence.
When a query occurs, the algorithm must return, in sorted order, the m smallest keys among all the keys that were input before the query. Assume that at least m keys are input before the first query occurs.
For example, suppose m = 3, and the key inputs and query operations occur in the following order:
20, 15, 31, 6, 13, 24, query, 10, 17, query, 9, 16, 5, 11, query, 14, ...
Then the first query should return 6, 13, 15; the second query should return 6, 10, 13; the third query should return 5, 6, 9.
Describe a simple algorithm that, for every m > 1, solves the above problem with the following worst-case time complexity:
- O(log m) to process each input key, and
- O(m) to perform each query operation.