CST370: Design and Analysis of Algorithms, Week 6

Week 6

This week we focused on AVL trees, 2-3 trees, heaps and heapsort, and hashing. Overall, I thought most of the material this week was pretty easy to follow.

AVL trees were probably easier than I expected. The main thing was remembering that the balance factor compares the height of the left subtree to the height of the right subtree. Once that made sense, the rotations felt less random. We worked through examples where inserting a new value caused part of the tree to become unbalanced, and then you had to figure out whether to use a left rotation, right rotation, or one of the double rotations to fix it.

The 2-3 trees were also pretty straightforward once I got used to the fact that a node can hold one or two values instead of just one. I liked seeing how values get promoted when a node becomes too full. The examples where we inserted values one at a time helped make that process easier to follow.

Heaps and heapsort made sense too. I understood the difference between a max heap and a min heap, and I thought the insertion and deletion examples were helpful. When adding a new value to a max heap, you keep swapping it upward until the heap property is restored. When removing the maximum value, you replace the root with the last value and then move it back down where it belongs.   

Hashing was probably the most complicated topic for me this week. I understand the overall idea of using a hash function to decide where a value should go in a table, but the modulus part is where I have to slow down. For example, if the table size is 100 and the key is 1234, you use the remainder to figure out the index. That part is not necessarily hard, but it adds another step where I have to make sure I did the math correctly before moving on. Collisions were another part of hashing that took a little more thought. We looked at separate chaining, where multiple values can be stored at the same index, and linear probing, where you move to the next available spot if the original index is already taken.