# Needs to Solve this Question

Please any one write the ans to this question,,,,

Q) Suppose one modifies the definition of an AVL tree in the following manner: The balance condition becomes |height(L(x)) &amp;#8722; height(R(x))| &lt;= 2, for each node x of the tree, i.e., the heights of the left and right subtrees have to differ by at most 2 (rather than at most 1, as

in 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)&gt;= c raisedto h  for an appropriate constant c &gt; 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.

Kemahiran:

Tentang Majikan:
( 0 ulasan ) New York, United States

ID Projek: #97685

inforexsys