CST 370 - Week 6 Learning Journal

 AVL Trees: 

AVL trees are a type of self-balancing binary search tree where the height difference (balance factor) between the left and right subtrees of any node is at most 1. When this balance is violated, rotations (left, right, left-right, right-left) are performed to restore balance. This ensures that operations like search, insertion, and deletion remain efficient at O(log n).

Questions: It is still difficult to determine which rotation (single vs. double) to apply in different imbalance cases. The conditions have many similarities which makes it difficult to differentiate. 

2-3 Trees: 

A 2–3 tree is a balanced search tree where each node can have either two children (2-node) or three children (3-node). Values are stored in a way that maintains sorted order, and the tree remains balanced by splitting nodes when they become too full. This guarantees that all leaves are at the same depth.

Heaps and Heapsort: 

A heap is a complete binary tree that satisfies the heap property (in a max-heap, each parent is greater than its children). Heaps are commonly used to implement priority queues. Heapsort uses a heap to sort elements by first building a heap and then repeatedly removing the maximum element and restoring the heap.

Questions: What are the implications for element order when considering heap structures during sorting?

Hashing: 

Hashing is a technique used to store and retrieve data efficiently using a hash function, which maps keys to positions in a table. Collisions can occur when different keys map to the same index, and these are handled using methods like separate chaining or open addressing.

Questions: How do you determine a good design for a hash function? I know that the keys needs to be distributed evenly but how do we put that into practice.