Insert, into an initially empty binary search tree, items with the following keys (in this order): 30, 40, 24, 58, 48, 11, 13, 50, 35. Then remove items 24 and 40 from the tree.
5, 2, 1, 6, 8, 3, 4
Now trace the effect of removing keys from the resulting tree, in the same order that they were inserted.
N
of items in
an AVL tree of height H
is Fib(H+3)-1
,
where Fib(K)
denotes the K
th
Fibonacci number.
(Hint: the recurrence relation for this was discussed in lectures,
and the textbook, so you just need to use induction to prove that
the solution to the recurrence is the shifted Fibonacci sequence.)
N
for a given
H
?