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