Binary Search: Precondition: 

Array is sorted Invariant: Key is in the range of begin to end Runtime: T(n) = T(n/2) + O(1) = O(log n) 
Can also be used for monotonic functions (always increasing) so can check foo(i) <= 10 so that i is minimum
PeakFind: Invariant: There exists a peak in the range of begin to end & every peak in begin to end is peak in 1 to n Runtime: O(log n)
Sorting
BogoSort: Choose a random permutation, if it is sorted, return it Runtime: O(n x n!)
BubbleSort: repeat n times, for (j: 1 to n-1) A[j] > A[j + 1], swap them Runtime: Best case: Already sorted O(n) Worst case: O(n 2)
Loop invariant: at end of j iterations, the biggest j items are correctly sorted in their final j positions (Stable)
SelectionSort: for (j: 1 to n – 1) find min A[j.. n], then swap in A[j] with A[min] Runtime: Both worst and best case is O(n2)
Loop invariant: after j iterations, the lowest j items are in first j positions (Not Stable) (Least swapping)
InsertionSort: for (j: 2 to n-1) take A[j] as key, insert key into sorted array A[1…j – 1] Runtime: Bestcase:Sorted O(n) worstcase: O(n2)
Loop invariant: after j iterations, the first j positions are sorted (Stable)
MergeSort: Divide and conquer Runtime: O(nlogn) for every case (Stable if merge is) Recurrence Relation: T(n) = 2T(n/2) + O(n)
Optimizations: Use insertionSort when array is mostly sorted (O(n)) or when there is smaller than 1024 items
QuickSort: Partition around a pivot Runtime: Worst case: increasing/decreasing array with fixed pivot (ie first/last) O(n 2)
Average Case: O(nlogn) if duplicates O(nlogk) k is distinct elements Recurrence Relation: T(n) = 2T(n/2) + O(n) -> partition O(n)
Loop invariant: A[pivot] all its left elems is less than it and all its right elems are more than it (Not Stable)

Order Statistics (QuickSelect) (Find kth smallest elem in unsorted array): partition around random pivot, take the pivots index,
index > the one we want, recurse on left, else recurse on right. (Partition until at least n/10 in each half of partition)
Loop invariant: i < p < j, A[i] <= A[p] < A[j], p is in its correct location in a sorted Array (Usually O(n) can be O(n2))
(Find k smallest/largest elements in order, use quickSearch for kth smallest, then quicksort index 1 to k, O(n + klogk)
Recurrence Relation: T(n) = T(n/c) + O(n)
Trees
Binary Search Trees: all in left sub-tree < key < all in right sub-tree MaxHeight: O(n)
SearchMax: recurse right till rightmost node Searchmin: recurse left till leftmost node Search: if key < node go left else go right
Runtime of Search: O(h) for BST is O(n) max runtime
Tree Traversals: In-Order: left -> self -> right, post-order: left -> right -> self, (Can be used to construct a BST)
Pre-order: self -> left -> right, Level Order Traversal: root, then its children and so forth. O(n) as visits every node
Successor O(h) (Key not in tree): Search for key in tree, if result > key, return result, if result <= key, search for successor of result
Successor (Key in tree): Case 1: node has right child -> right.searchMin()
Case 2: node has no right child -> go up tree till parent is null or child is a left child of the parent, parent is the successor
Delete O(h): Case 1: no children, just delete Case 2: 1 child, delete and connect parent with the child
Case 3: 2 children, delete and replace with successor
Balanced Trees (Height: O(log n) and all operations run in O(log n)) Perfectly balanced, at every step, there is a left and right half
AVL trees: Every node height balanced, node is height balanced if |v.left.height - v.right.height| <= 1 (h < 2 n/2 and n > 2h/2 )

Left-left: Right rotate(x)

Left-Right: Left-rotate(x.left), Right-Rotate(x)
Right-Right: Left rotate(x)
Right-Left: Right-rotate(x.right), Left-rotate(x)
Weight update: recompute by looking at
subtrees aft rotation (update by walking UP)

*Not all balanced trees are height balanced as can add extra level to balanced tree but all height balanced trees are balanced
Left-Heavy: left subtree has larger height than right subtree. Right-Heavy: right subtree has larger height than left subtree
Insert O(h): Maintain balance, find lowest node on leaf to root path that violates balance property and rebalance (At most 2 rotates)
Delete O(h): Maintain balance, go up the leaf to root path to find EACH node that violates and rebalance
Tries(Used to store Strings mostly): Search: O(String length), Space: O(Size of text), faster than AVL but uses more overhead cost
Can be used to query prefix, longest prefix, wildcards (find strings with l??p)
Augment Data Structure: Data structure, determine additional info & modify structure for it, make new operations
When adding new info, remember to maintain it during rotations, insertions and deletions
Dynamic Data Structure: Build, Operations that modify: insert, delete, Query Op: Search, select etc
Order Statistic Trees: Store weight at every node, rank of node = weight of left subtree + 1
(Used when need count elems smaller/larger than value, in O(log n) time)
Select(rank): if rank == left.w + 1, done, if rank < left.w + 1, go left, if rank > left.w + 1, update rank = rank – (left.w + 1) and go right
Rank(node): rank = v.left.weight + 1, if left child: v = v.parent;, if right child, rank += v.parent.left.weight + 1; v = v.parent
To maintain Weight: go from leaf to root to update, but don’t forget to rotate first
Interval Tree: each node is an interval, sorted by left-end pt, contains maximum endpoint in subtree
(Used to find intervals that overlap with point/interval)
Search(x): from root, if x > v.left.max or v.left == null, go right, else go left, end when x is in interval/reach null (Ologn)
Range Trees(1D): Each node stores max of any leaf in left subtree, all leaves are points (to find points which are in a range)
find splitnode (inbetween range), traverse left then right.
Left: if range-low <= v.key, traverse all in right, recurse on left. Else recurse on Right,
Right: if range-high >= v.key, traverse all on left, recuse on right, else recurse on left. (takes O(k + log n))
(Used when finding range in more than 1D, and it is faster than kd-trees for lower dimensions)
Stacks: FILO Queues: FIFO