Data Structures Final

Sorting algorithms 2 methods

merge sort and quick sort

merge sort

divide and conquer methods that splits list into two halve, then sorts each side, then merges them back together

quick sort

finding pivot, then creating two subarrays: elements less than pivot, elements more than pivot.

best care quick sort

divides into equal halves (O(n log n))

average case quick sort

randomized pivot selection trying to balance sides (O(n log n))

worst case quick sort

when pivot is last or first element, or when all elements are the same (O(n²))

quick sort space complexity

recursive call stack(depth of recursion tree) (O(log n))

best/average/worst merge sort

always divides into two halves, good preformance regardless

merge sort space complexity

requires extra temporary arrray, not in-place like quick sort

Whats a heap

binary tree based data structure that fufills heap property/a complete binary tree:

• Max-Heap: Parent node ≥ Children (root = max element).

• Min-Heap: Parent node ≤ Children (root = min element).

• Shape Property: Must be a complete binary tree (filled left to right).

How to store a heap

heaps are stored in arrays (left to right)

heapify procedure

fix a single violation in a heap tree. (compare parent with children, switch according to max or min heap, then recursively heapify)O(log n)

heapify insertion

increase heap size, add new element to last node (heapify upwards) O(log n)

Heap deletion

remove root max/min, replace with last node, heapify according to heap property

heapsort

comparison base sort using heap (build heap, repeatedly extract max/min and place at end, do so until max=ascending or min=decending

min heap

root node is minimum

max heap

root node is maximum

Binary tree

a tree that can have a max of 2 children

full binary tree

node is a leaf posesses two children

complete binary tree

all nodes have 2 children until last level, last level only have children on left side

perfect binary tree

all internal nodes havwe two leaves and leaves are all even. (N= 2^h – 1) N = nodes, h= tree height

Balanced binary tree

diffrence between HR and HL is not more than 1

in-order traversal

left→root→right

preorder traversal

root→left→right

postorder

left→right→root

BST

Binary search tree, has at most 2 children, left child is smaller than node, right value is larger than node

BST search

finding values using its sorted structure. Compare target with current node: h the current node:

• If equal → Found!

• If target < node value → Search left subtree.

• If target > node value → Search right subtree.

BST insert

start at root, compared in BST form until null spot found

BST delete

no children - delete

1 child - replace node with its child

2 children - replace node with largest in left side or smallest in right side

Time complexity BST Worse case

O(h), h is binary tree height

Why are balanced binary trees good

automatically keeps height small so operation takes less time

AVL tree

self balancing tree

AVL insertion

same as BST

Hashing

changes data to fixed values for efficieny

Hash Function (modulo division)

way to map array keys to hash tables, ndex=key % TableSize

Collision

two different keys produce same hash value, pigeon hole = more keys than hash table slots means sharing must occur,

Linear probe

solution for collision, looks for next available slot sequentially

quadratic probe

sollution for collision, looks for next available slot using quadratic jumps

Double hashing

solution for collision, two hashing values are used to find one key, first is used to compute intital value, second is for computing step size for probing

chaining

solution for multiple collisions, implement array as linked list like chain