Data Structures: Sorting, Hashing, and Tree Traversals

Tree Traversal Methods

Preorder traversal: Visit the root, visit the left subtree, and then visit the right subtree.

Inorder traversal: Visit the left subtree, visit the root, and then visit the right subtree.

Postorder traversal: Visit the left subtree, visit the right subtree, and then visit the root.

Breadth-First Traversal: Visit the root, visit the children of the root (left to right), and then the children of the children (left to right), going down level by level.

Depth-First Traversal: Rather than visiting the tree level-by-level like in breadth-first traversal, visit the root, go all the way down the left on one path, and then move across the tree to the right, going down all the paths until the end.

Hashing and Collision Resolution

Hashing: The technique used for ordering and accessing elements in a collection in a relatively constant amount of time by manipulating the element's key to identify the element's location in the collection.

Hashing typically provides O(1) operation implementation.

Hashing uses arrays to hold key/value pairs.

Two Collision Resolution Policies

• Linear probing: Store the colliding entry into the next available space.
• Quadratic Probing: The value added at each step is dependent on how many locations have already been inspected.

Tree Manipulation and Array Indexing

What is necessary to do in order to manipulate a tree? You must be able to find the left and right child of a node in the tree.

Finding Children and Parent Nodes

• The elements[index] left child is in elements[(index * 2) + 1].
• The elements[index] right child is in elements[(index * 2) + 2].
• The elements[index] parent is in elements[(index - 1) / 2].

Sorting Algorithms and Complexity

Simple Sorting Algorithms

• Bubble Sort: The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
• Selection Sort: The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
• Insertion Sort: To sort an unordered list of elements, we remove its entries one at a time and then insert each of them into a sorted part (which is initially empty).

Insertion Sort Best Case: The data are already sorted in ascending order.

Divide-and-Conquer Sorting

Merge Sort: Merge sort is based on the divide-and-conquer paradigm. It involves the following three steps:

1. Divide the array into two (or more) subarrays.
2. Sort each subarray (Conquer).
3. Merge them into one in a smart way.

Quick Sort: At each stage, the part of the array being sorted is divided into two "piles," with everything in the left pile less than everything in the right pile. It does not require an auxiliary array.

Algorithm Complexity Comparison

Simple Sorts (O(N²)):

• Selection Sort - O(N²)
• Bubble Sort - O(N²)
• Insertion Sort - O(N²)

Efficient Sorts (O(N log N)): Merge Sort, Quick Sort, and Heap Sort.

Quadratic Probing Example

If given 5 numbers between 0-99, put them into a hash table using the formula: H(i) = i mod (size of table).

Example: If i = 76 and the table size is 100, then H(76) = 76 mod 100 = 76, so 76 goes in index [76].