That Stuff Flashcards
Binary trees
BST
AVL
- 2 children
- Left < x < Right
- Height Limit
Depth
Top down
Height
Bottom up
Single Rotation
Move subtree
Double rotation
- X and grandchild
- X and child
B Trees
- Path is like streets to data
- Data is in leaves
- O(N log N)
Load Factor
- # of Items / Table Size
- O(N/M)
- Rehash if λ >= 3/4
Binary Heap / Priority Queue
- A full binary tree
- [2i] - [i/2] - [2i+1]
-perlocateDown
d Heaps
-Heap with d children
- Insert O(log_d N)
- Delete d-1 comparions
Merge Heaps Types
Leftist < Skew < Binomial
Insertion Sort
- O(N) to O(N^2)
- Read i, insert, read i,…
- N < 20
Shell Sort
- Long one
- Distance = Lenght/2
- O(N^3/2) to O(N^2)
Merge Sort
- Split, Combine
- O(N log N)
Quick Sort
- Pivot = 3 median
- Smaller < x < Larger
- O(N logN) to O(N^2)
Partitioning
Compare two outer pivots and move inwards
Connected Graph
All nodes have an edge
Adjacent Matrix
A[i][j]
i is adj to j
Dense graphs
Ω(V^2)
Complete Graph
Every node is linked
Vertex count
Directed 0 < E < V(V-1)
Undirected 0 < E < (V(V-1)) / 2
Sparse E = V
Dense E = V^2
Adjecent List
Like Heap
Store undirected nodes twice
Sparse graphs
Ω(V + E)
Topological Sort
- Find vertex with indegree = 0
- Print v
- Delete v + edges
- Queue children if indegree = 0
Hamiltonian Cycle
Visits every vertex once
Path Runtime
+ O(E logV)
- O(EV)
P Complexity
Easy to solve and confirm
NP Complexity
Difficult to solve, easy to confirm
EXP Complexity
Difficult to solve and confirm
B Trees
d Heaps
- O(N logN)
- O(log_d N)
Insert Sort
Merge Sort
Shell Sort
Quick Sort
- O(N) to O(N^2)
- O(N logN)
- O(N^3/2) to O(N^2)
- O(N logN) to O(N^2)
Adj Matrix
Adj List
- Ω(V^2)
- Ω(V + E)
Path Runtime
+ O(E logV)
- O(EV)
