Week 65: CST370 - Design and Analysis of Algorithms

 WK06: Weekly Reflection

This week's module focused on AVL trees, 2-3 trees, heaps and Heapsort, and hashing. These topics helped me understand how different data structures maintain organization and efficiency when storing, searching, inserting, and removing data. I also learned how balancing, restructuring, and choosing an appropriate storage method can improve the performance of algorithms.

One topic that stood out to me was the AVL tree. I learned that an AVL tree is a self-balancing binary search tree in which the heights of the left and right subtrees must remain balanced. The balance factor of each node is calculated by comparing the heights of its subtrees. When the balance factor becomes too large or too small, rotations are used to restore the tree’s balance. The exercises helped me practice identifying whether a binary search tree was also an AVL tree.

The AVL tree operations were especially useful because they showed how rotations maintain efficient performance. I learned about single rotations, including left and right rotations, as well as double rotations, such as left-right and right-left rotations. At first, deciding which rotation to use was challenging, but the examples and visualization helped me see how the position of the newly inserted node determines the required rotation. My main takeaway was that keeping the tree balanced prevents it from becoming similar to a linked list and allows searching, insertion, and deletion to remain efficient.

The materials on 2-3 trees introduced another type of balanced search tree. I learned that a 2-3 tree can contain nodes with either one key and two children or two keys and three children. Unlike a standard binary search tree, all leaves in a 2-3 tree remain at the same level. When a node becomes full during insertion, it may need to be split, and a value is promoted to the parent node. This structure showed me another way of maintaining balance without using rotations.

Another important topic was heaps. I learned that a heap is a complete binary tree that follows a specific ordering property. In a max heap, the value of each parent is greater than or equal to the values of its children, while a min heap follows the opposite rule. The exercises on adding and removing values from a max heap helped me understand how elements move upward or downward to restore the heap property. I also learned that heaps are commonly represented using arrays, which makes it possible to locate parent and child nodes using index calculations.

The Heapsort materials showed how a heap can be used to sort data efficiently. The process begins by transforming an unsorted array into a heap. The root value is then repeatedly exchanged with the last available element, removed from the active heap, and placed in its correct sorted position. After each removal, the heap must be restored. The bottom-up heap construction method was useful because it demonstrated how a heap can be built by starting with the internal nodes and applying the heapify operation.

Hashing was another topic that helped me understand efficient data storage and retrieval. I learned that a hash function converts a key into an index in a hash table. This allows values to be inserted and searched without examining every element. However, collisions can occur when multiple keys are assigned to the same index. The lectures explained that collisions can be handled through methods such as separate chaining or open addressing.

I also learned about the load factor and rehashing. The load factor compares the number of stored elements with the size of the hash table. As the table becomes more crowded, collisions become more frequent and performance may decrease. Rehashing solves this problem by creating a larger table and inserting the existing values again using the new table size. The practice problems and puzzle helped reinforce how hashing can be applied to real problems involving counting and organizing data.

Overall, this week helped me understand how different data structures are designed to maintain efficiency. AVL trees use rotations to remain balanced, while 2-3 trees use node splitting and promotion. Heaps organize values according to priority and provide the foundation for Heapsort. Hash tables use hash functions to support fast insertion and searching while managing collisions and table capacity. My main takeaway is that the organization of a data structure has a major effect on the efficiency of the algorithms that use it.