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. 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(n2) time!) for counting the number of 1's in A.