CSE 326 Section I

BS and AVL Trees

Karen Liu

4/13/00

 

  1. Show that the maximum number of nodes in a binary tree of height h is 2^(h+1) - 1.
  2. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
  3. Write a procedure to implement single rotation for AVL tree.
  4. Write a procedure to implement double rotation for AVL tree.
  5. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.
  6. How to implement deletion in AVL trees?
  7. Give a precise expression for the minimum number of nodes in an AVL tree of height h.
  8. What is the minimum number of nodes in an AVL tree of height 15?
  9. Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on.
  10. Write a function that list out the nodes in a binary tree in an ascending order of key fields.
  11. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree.
  12. Write a function to test the equality of two binary trees.

bool equal(tree_pointer t1, tree_pointer t2);

  1. Assume that each node in an AVL tree t has the filed lsize. For any node, a, a->lsize is the number of nodes in its left subtree plus one. Write an algorithm avl_find(t, k) to locate the kth smallest identifier in the subtree t. Show that this can be done in O(logn) time if there are n nodes in t.
  2. Write a function swap_tree that takes a binary tree and swaps the left and right children of every node.