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

## Solution

## 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

Draw the following tree after a

**left**rotation at the**node 25**.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.**

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, 2, 3, 5, 4
- 15, 3, 9, 8, 14, 13, 12, 11, 10
- 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.

- F L A M E T H R O W I N G
- T A N K F U L S Z E R O
- 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.

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