IC312: Data Structures (FA16)

Home Policy Calendar Units Assignments Resources

HW 6: AVL's and 2-3-4 Trees

Solution

You can find the long form of the solution here, or just the answers (no step-by-step) here.

Overview

This is a written homework assignment. It is due in class, in hard-copy.

Due Date

This homework is due Friday 21, October in class

Grading

The assignment is graded out of 100 points. Each question is worth 10 points.

Submission and Starter Code

Submission must occur in hard copy at the start of class.

Problems

AVL Tree Problems

  1. Draw the following tree after a left rotation at the node 25.

    prob1.png

  2. Copy the following tree and write the balance factor of each of the nodes. If there is any node out of balance, perform the rotation(s) that will create an AVL tree. You must show the tree after each rotation if there are multiple rotations.

    prob2.png

For the next questions: Start with an empty AVL tree and insert each of the given nodes in the order given. Rebalance after each insertion. You do not need to draw each insertion separately, but you must draw the tree immediately before every rotation and say what the rotations are.

  1. 1, 2, 3, 5, 4
  2. 15, 3, 9, 8, 14, 13, 12, 11, 10
  3. 77, 82, 2, 25, 54, 27, 21, 95, 65

2-3-4 Tree Problems

For the next two problems, starting with an empty 2-3-4 tree, insert each of the given letters into the tree, in the order given. Show your work, and clearly indicate the final state of the 2-3-4 tree after all the insertions.

  1. F L A M E T H R O W I N G
  2. T A N K F U L S Z E R O
  3. L U M B E R J A C K

For the next two problems, I mostly need the final answer, but you need to show your work That might mean showing the series of trees that you made to find the answer, or explaining how else you figured it out. Of course, you should clearly indicate your final answer.

  1. Starting with an empty 2-3-4 tree, and inserting the letters of the alphabet A, B, C, D, … in order, the first time the tree would grow to height 1 would be after inserting D. After inserting what letter would the tree grow to height 2 for the first time?
  2. Now answer the same question, but for height 3. So, starting with an empty tree and inserting A, B, C, … in order, after inserting what letter would the tree grow to height 3 for the first time?

Bonus Problem (+5 points) Come up with an exact formula for the maximum number of nodes in a 2-3-4 tree of any height \(h\), if insertions are performed the way we did it in class.