1 < log n < n < n*logn < n^2 < n^3 < 2^n < n!

AVL Trees: For every node, the heights of its left and right subtrees differ by at most [Link] balance factor of a node is
defined as height(left) – height(right) , which must be –1, 0, or +1 in an AVL tree. To maintain this, insertions and deletions
perform tree rotations. AVL trees guarantee height h=Θ(log n) and hence all dictionary operations (search/insert/delete) take
worst-case O(log n) time.
Search: Same as in a BST; cost O(h)=O(log n). Insertion: Perform one of four rotations (LL, RR, LR, RL) at the lowest
unbalanced node (the pivot). In an LL case do a single right rotation; in an LR case, do a left rotation on the child then a right
rotation on the pivot. RR - rotateLeft, RL - rotateRight,rotateLeft. Rotate O1
Deletion: Similar to BST deletion followed by rebalancing. After removing a node, traverse up and perform rotations if any
ancestor’s balance factor is ±2. (For brevity, detailed pseudocode is omitted.) Complexity: Worst/average/best-case for
search, insert, delete are all O(log n). Space is O(n), with each node storing a height (or balance factor).
Use-Cases: Use AVL trees when you need strict balancing and guaranteed fast lookups (e.g. inmemory ordered maps). They
ensure O(log n) worst-case per operation. In practice they may beslower than some alternatives due to more rotations.
Node* rotateRight(Node* y) Node* rotateLeft(Node* x)
{ {
Node* x = y->left; Node* y = x->right;
Node* B = x->right; Node* B = y->left;

x->right = y; y->left = x;
y->left = B; x->right = B;

updateHeight(y); updateHeight(x);
updateHeight(x); updateHeight(y);

return x; return y;
} }

Splay Trees A splay tree is a self-adjusting BST that “splays” (moves) any accessed node to the root via [Link] has no
explicit balance factor; instead, frequent accesses to certain keys tend to keep those keys near the root. Splay trees achieve
amortized O(log n) time for search/insert/delete over a sequence of operations , though a single operation can be Θ(n) in the
worst case. In fact, any sequence of m operations takes O(m log n) time total
Search : O(log n) to O(n). Invoke splay(x) . This performs bottom-up rotations (zig, zig-zig, zig-zag) until x is at the root. If x
was in the tree it ends at the root ; otherwise the last accessed node is splayed. Insertion: First splay(x) . If x is already root
(equal key), you may handle it (e.g. update value) and stop. Otherwise x is not in the tree: let T be current root with key y.
Create a new node x as the new root, with left subtree L = nodes ≤ x (which was T’s left subtree) and right subtree R = nodes
≥ x (which was T’s right subtree) . Concretely, if x < y, let R = old root and set L = [Link]; else vice versa. This effectively
splits the tree at x and attaches.
Deletion: Splay x to root. If root’s key ≠ x, it’s not present. Otherwise remove the root: let L = [Link], R = [Link]. If L is
null, return R as new root; else splay the maximum key in L to make it root, and attach R as its right child. Amortized cost:
Each operation is amortized O(log n .In particular, any sequence of m searches/ inserts/deletes takes O(m log n) time This
amortization relies on the fact that deep nodes are brought up, flattening long paths over time.
Use-Cases: Splay trees work well when access patterns have locality (recently accessed items are likely to be accessed
again). They are simpler to implement (no balance info) and adapt to nonuniform access. Typical use-cases include cache
implementations or as part of advanced sequence data structures.

B Tree of degree t has(min children of a non-root node = t; max children = 2t, min key = t-1, max key = 2t-1). order m
has(max children = m, max key = m-1, min children = ceil(m/2), min keys = ceil(m/2) - 1). Order = 2*degree
Heap -> array là level order traverse (BFS) đi từ root -> hàng 1 (left to right) -> hàng 2(left to right). Parent (i-1)/2, left child
= 2i+1, right child = 2i+2
- Khi xóa root thì thay root bằng element ở cuối array, xong heapify từng step, mỗi step thì swap node hiện tại với children
nhỏ nhất
- khi insert thì insert vào cuối array, sau đó so sánh với parent rồi swap
- find min là O(1); insert, del min, heapify đều là O(log n); build heap là O(n)

Tree Traversals Tree traversal algorithms visit all nodes in a tree in a systematic order. In a binary tree T, common
traversals are:
Preorder: Root, left, right. Inorder: Left, root, right. (For BSTs, this yields sorted order.). Postorder: Left, right, root
All tree traversals are Θ(n) time on a tree of n nodes. Space is O(h) stack for recursive DFS or O(n) queue for level-order.
Preorder: 4,2,1,3,6,5,7.
Inorder: 1,2,3,4,5,6,7.
Postorder: 1,3,2,5,7,6,4.
Level-order: 4,2,6,1,3,5,7.

Graph Representations A graph G=(V,E) can be represented as: Complexity, addV, addE = O(1); delEgde = O(degree);
delVertex, BFS, DFS, search = O(V+E)
Topological Sort: for directed graph, no cycle, usage for: courses at university, lessons in textbook,….
Adjacency List: For each vertex, a list of neighbors. Space Θ(|V|+|E|). Efficient for sparse graphs. Checking adjacency of u,v
takes O(deg(u)).
Adjacency Matrix: A |V|×|V| boolean or weight matrix. Space Θ(|V|²). Good for dense graphs or for constant-time edge
checks. Typical trade-off: use lists if |E|≈|V|, matrices if graph is dense (|E|≈|V|²).
Breadth-First Search (BFS): Starting from a source vertex for each u in G.V:
s, BFS explores neighbors level by level using a queue. It [Link] = white
finds shortest paths (in edge count) from s. Each edge and [Link] = ∞
vertex is explored once, so time is Θ(| V|+|E|) [Link] = gray; [Link] = 0
procedure BFS(G, s): Q = new Queue; enqueue(Q, s)
while Q not empty: [Link] = white
u = dequeue(Q) for each u in G.V:
for each v in Adj[u]: if [Link] == white:
if [Link] == white: DFS-Visit(u)
[Link] = gray procedure DFS-Visit(u):
[Link] = [Link] + 1 [Link] = gray
[Link] = u for each v in Adj[u]:
enqueue(Q, v) if [Link] == white:
[Link] = black [Link] = u
Use-case: Shortest path in unweighted graphs, finding DFS-Visit(v)
connected components, building level-ordered [Link] = black
iterators. DFS also takes Θ(|V|+|E|) time
Depth-First Search (DFS): Recursively explores as far as Use-cases: topological sorting (in DAGs), cycle detection,
possible along each branch before backtracking. Use stack finding connected components or strongly connected
Pseudocode: components, and in algorithms like finding articulation
procedure DFS(G): points.
for each u in G.V:
Dijkstra’s Algorithm: For nonnegative weights. Uses a min-priority queue. Initializes distance d[s]=0, others ∞, then
repeatedly extracts the nearest unsettled vertex u and relaxes its outgoing edges. Use when: Edge weights ≥ 0, Need
shortest route from one source, Road maps, GPS navigation, Network routing…
Idea: dist[source] = 0 Complexity: O(|E| log |V|) with a binary heap or adjacency
Pick smallest distance vertex list
Relax its neighbors -> Repeat .Using a Fibonacci heap improves to O(|E| + |V| log |
V|).Space O(V)
Bellman–Ford Algorithm: Handles negative edge weights (detects negative cycles). Repeatedly relaxes all edges up to |V|–
1 times.
function BellmanFord(G, w, s): if d[u] + w(u,v) < d[v]:
for each u in G.V: d[v] = d[u] + w(u,v); parent[v] = u
d[u] = ∞; parent[u] = NIL // Check for negative cycle
d[s] = 0 for each edge (u,v) in G.E:
for i = 1 to |V|-1: if d[u] + w(u,v) < d[v]:
for each edge (u,v) in G.E: report “negative cycle exists” and exit
Complexity: Θ(|V||E|) worst-case . It is slower than Dijkstra’s but handles negative edges. Space O(V)
Use-case: Graphs with negative edge weights (but no negative cycles), e.g. some currency arbitrage detection, certain
scheduling problems.
Floyd-Warshall Algorith: Computes shortest path between: EVERY pair of vertices Not just one source.
When to use? Need: All-pairs shortest path Examples:Airline route analysis City-to-city distances Network analysis
Best Usage: Small to medium dense graphs. Compexity: Time O(V^3) Space O(V^2)
Pseudocode:
FloydWarshall(G):
dist = adjacency matrix
for k = 1 to V
for i = 1 to V
for j = 1 to V
dist[i][j] =
min(
dist[i][j],
dist[i][k] + dist[k][j]
)
Minimum Spanning Trees (MST)
Spanning tree is a tree has all the vertices of the graph (V vertex), no cycle, and make sure we can reach every vertex we
want
Given a connected undirected weighted graph, an MST is a subset of edges connecting all vertices with minimum total weight.
Two classic algorithms:
Kruskal’s Algorithm: Sort all edges by weight, and add Prim’s Algorithm: Grows a single tree by repeatedly
them one by one (using a disjoint-set/union adding the smallest-weight edge that connects
find to avoid cycles). the tree to a new vertex.
function Kruskal(G): Pseudocode:
A = {} // MST edge set function Prim(G, w, r):
make-set for each vertex for each u in G.V:
sort edges of G by weight key[u] = ∞; parent[u] = NIL
for each edge (u,v) in sorted order: key[r] = 0
if find-set(u) ≠ find-set(v): Q = a priority queue of all vertices keyed by key[u]
A = A ∪ {(u,v)} while Q not empty:
union(u,v) u = extract-min(Q)
return A for each edge (u,v):
Complexity: Dominated by sort: O(|E| log |E|) = O(|E| log | if v in Q and w(u,v) < key[v]:
V|) parent[v] = u
(assuming union-find is nearly linear). key[v] = w(u,v)
Use-case: When edges can be efficiently sorted (sparse decrease-key(Q, v, key[v])
graphs). It finds an MST or minimum spanning Fig.: Prim’s algorithm for MST.
forest if graph is disconnected. Complexity: Using a binary heap and adjacency list, O(|E|
log |V|)
. (Using a Fibonacci heap yields O(|
E| + |V| log |V|)).
Use-case: Dense graphs or when one wants a single-tree
growth (e.g. network design).