pshah01
October 14th, 2006, 03:19 PM
Suppose one modifies the definition of an AVL tree in the following manner: The balancecondition becomes |height(L(x)) − height(R(x))| 2, for each node x of the tree, i.e., theheights of the left and right subtrees have to differ by at most 2 (rather than at most 1, asin the standard definition). Working with this modified definition:
(a) Draw one legal AVL tree and one illegal AVL tree.
(b) If n(h) is the smallest number of nodes in an AVL tree of height h, write a recurrence defining n(h).
(c) From the above recurrence, deduce that n(h) ch, for an appropriate constant c > 1.
(d) Explain how the fact that n(h) is at least exponential in h implies that the balance condition given above forces the tree to be “balanced,” i.e., to have height O(log n), if n is the number of nodes in the tree.
Please suggest me the ans for this Q.........thanx in advanced.
(a) Draw one legal AVL tree and one illegal AVL tree.
(b) If n(h) is the smallest number of nodes in an AVL tree of height h, write a recurrence defining n(h).
(c) From the above recurrence, deduce that n(h) ch, for an appropriate constant c > 1.
(d) Explain how the fact that n(h) is at least exponential in h implies that the balance condition given above forces the tree to be “balanced,” i.e., to have height O(log n), if n is the number of nodes in the tree.
Please suggest me the ans for this Q.........thanx in advanced.