CST370 - Week 6

This week we moved on to learning about different types of trees. We started learning about AVL trees. They are BST trees that must keep a balance factor of -1, 0, or 1. If a node is inserted that causes the balance factor of a node to not fit in this range, rotations must be done. These can be a little confusing to do, but the video explained it clearly and thoroughly. Next, we looked at 2-3 trees in which nodes can hold 1 value and have 2 children, or 2 values with 3 children. All leaves of a 2-3 tree must be on the same level. We then went into heaps and heapsort. Heaps are an efficient implementation of a priority queue and are complete binary trees with every level completely filled (or filled up on the left side for the last level). We can also have max heaps and min heaps in which a parent is greater or smaller than its children. Lastly, we learned about hashing and the two methods to handle collisions: linear probing and separate chaining.

Our first homework program conducted various heap operations such as insert, displayMax, update, delete, and display. The next program showed results of the time performance of three different algorithms: heap sort, merge sort, and quick sort. The last assignment was offered for extra credit and it was to write a program to do hashing with linear probing. I started working on this but didn't end up finishing it, so I just gave in what I had.