CST 370 - Week 6

This week covered several foundational data structures, and each one helped me understand how different trees and hashing techniques maintain efficiency.

AVL trees are self‑balancing binary search trees. I learned how to identify the height of each node and how imbalances occur when the height difference reaches values like other than 1,0, or -1. The most interesting part was seeing how rotations restore balance. Visualizing these rotations made the idea of maintaining logarithmic height feel much more intuitive.

We also explored 2‑3 trees, a type of search tree I hadn’t encountered before. I didn’t know a node could store two values, so seeing how that affects searching and insertion was interesting. Constructing these trees step‑by‑step helped me understand how values get promoted and how the tree keeps all levels perfectly balanced. It’s a very different structure from binary trees, but the consistency across levels makes the logic feel clean once you get the hang of it.

Next, we were introduced to heaps, specifically max heaps. A max heap requires every node to be greater than or equal to its children, and we practiced checking whether a given tree satisfied that property. The concept was easier to understand on paper, but, working through the homework was a bit of a challenge.

We also covered collision handling in hashing, focusing on linear probing and separate chaining. This week’s homework used linear probing, and I actually enjoyed applying the concept in code.

Finally, we learned about load factor and rehashing. When the load factor reaches a certain threshold, the table expands to $2n$ and then adjusts to the next prime number. I still want to research why the next prime is chosen, but I understand the general idea.