Balanced Search Trees
Table of Contents
This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should write up your own assignment.
We will use anonymous grading on Moodle, which means that the grader won't see your name until after the grading is done. This is an easy way to help add an extra element of fairness to the grading. Therefore, make sure your name doesn't appear on your actual submission. When you submit via Moodle, it will know you are. Thanks!
Turn in your answers electronically. Most of this assignment involves drawing trees, which is faster and easier to draw by hand than to use software. Feel absolutely free to write out your solutions by hand, and either scan using a scanner at the library (or elsewhere) or take a quality picture of it before submitting. You're also welcome to draw them using software if you like.
1. AVL Tree
Draw the AVL tree that results after inserting, in this order, the following integers:
10, 20, 30, 40, 50, 25, 5, 3, 23, 27, 21
Show each AVL tree after each insertion. In other words, you should be submitting drawings of 10 trees, each one of which has successively one additional item in it.
2. 2-3 Tree
Repeat the above exercise, but use a 2-3 tree instead of an AVL tree.
3. Example Trees
- Draw the shortest possible AVL tree that contains 20 values.
- Draw the shortest possible 2-3 tree that contains 20 values.
- Draw the tallest possible AVL tree that contains 20 values.
- Draw the tallest possible 2-3 tree that contains 20 values.