##BST
Nodes that are smaller go to the left, nodes that are larger go to the right
###Average-case
- Search:
O(logn) - Insert:
O(logn) - Remove:
O(logn)
###Worst-case (linked list)
- Search:
O(n) - Insert:
O(n) - Remove:
O(n)
##Red-Black Tree
-
Three invariants: Root is black, all leaves are black, can't have two red nodes at once, insert new node as red and adjust
-
By keeping it all balanced, we're guaranteed the average-case that BST couldn't guarantee
-
Search:
O(logn) -
Insert:
O(logn) -
Remove:
O(logn)
##Hash Table
- chaining: make a linked list at each value to store multiple values in one key
- use hashing function to turn whatever value we put in into a key
###Average/best-case
- Search:
O(1) - Insert:
O(1) - Remove:
O(1)
###Worst-case (when all hash to the same value)
- Search:
O(n) - Insert:
O(n) - Remove:
O(n)
##Graph BFS
- Maintain a visited array and a queue
- Enqueue start node and mark it visited
- As long as the queue has something, dequeue it and check if it's the one we want, mark all of its neighbors as visited, then - enqueue all the neighbors
O(|E| + |V|)- travel all the edges and vertices
##Graph DFS
- For each node, if it's not visited, mark it visited and recursively vist all the unvisited neighbors
- Return in the recursive function call if it's the one we want
O(|E| + |V|)- travel all the edges and vertices
##Graph Dijkstra's
-
Put all nodes in a priority queue with infinite cost
-
Put the start node with zero cost
-
Until you find your end node:
-
Call extractmin to pull the lowest cost and check if it's the one you want
-
Update all the neighbors costs with the current cost + weight of the edge connecting the two
-
If the new cost is lower than the old cost, reset the neighbor's cost to this new cost and set the neighbor's predecessor to this node
-
This is
O((|E| + |V|)logV)
##Heap
- Each parent node must be larger than both of its child nodes
- All operations are
O(logn)
##Priority Queue
##Quicksort
- Pick a pivot and partition into left right
- Repeat for the left and right halves
O(n^2)if you only sort one element at a time (first, last, etc.)O(nlogn)otherwise (each split = logn levels, n elements each leve)
##Heapsort
- Make a max-heap
- Swap max with the last leaf
- Heapify down
O(nlogn)- n elements, each call to extractmax is logn because of heapify