关于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.