COMP2011 Tutorial Exercises 7, Week 8

Binary Search Trees, AVL Trees

Tutorial Questions

1. 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.

2. Trace the effect of inserting keys into an initially empty AVL Tree in the following order. Depict the state of the tree before any required rotations (showing where the tree is out of balance), and the final state of 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.

3. • Show that the minimum number N of items in an AVL tree of height H is Fib(H+3)-1, where Fib(K) denotes the Kth 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.)
   • What is the maximum number N for a given H?
   • For a tree with 1023 (= 2¹⁰ - 1) items what is the minimum height? the maximum?
   • For a tree with 1048575 (= 2²⁰ - 1) nodes what are the minimum and maximum?

4. C-8.13 Suppose that each row of an n x n array consists of 1's and 0's such that, in any row of A, all the 1's come before any of the 0's in that row. Assuming A is already in memory, describe a method running in O(n log n) time (not O(n²) time!) for counting the number of 1's in A.