PENALGO

Giao diện

Cấu trúc phi tuyến — Tree, Heap & Graph ​

Array và Linked List mô tả dữ liệu tuần tự — từng phần tử xếp hàng trước sau. Nhưng thế giới thực không tuyến tính: cây thư mục (Tree), hàng đợi ưu tiên trong bệnh viện (Heap), mạng lưới đường bay (Graph). Ba cấu trúc phi tuyến này là nền tảng cho mọi thuật toán quan trọng: BFS, DFS, Dijkstra, Dynamic Programming trên cây, và hàng tá bài phỏng vấn.

🎯 Mục tiêu

Sau bài này, bạn sẽ:

  • Nắm vững 4 traversals trên Binary Tree (inorder, preorder, postorder, level-order)
  • Hiểu BST property và tại sao degenerate tree = linked list
  • Biết heap property, swim/sink, và TẠI SAO heapify là O(n) không phải O(n log n)
  • Phân biệt adjacency list vs adjacency matrix — khi nào dùng cái nào
  • Xây dựng trực giác về graph vocabulary: degree, path, cycle, connected component

Phần 1 — Binary Tree ​

Bức tranh tư duy ​

Một Binary Tree là cấu trúc phân cấp: mỗi node có tối đa 2 con (left, right). Hãy hình dung cây gia phả lật ngược — gốc ở trên, lá ở dưới.

            [15]              ← root (gốc)
           /    \
        [10]    [20]          ← level 1
        /  \    /  \
      [5] [12] [18] [25]      ← level 2 (leaves — lá)

Thuật ngữ cốt lõi: Root — node trên cùng. Leaf — node không có con. Height — số cạnh dài nhất từ root → leaf. Depth — số cạnh từ root → node hiện tại. Subtree — bất kỳ node nào cùng toàn bộ hậu duệ.

Binary Search Tree (BST) Property ​

BST thêm một ràng buộc vào Binary Tree:

  • Left subtree: mọi giá trị < parent
  • Right subtree: mọi giá trị > parent
  • Hệ quả quan trọng: Inorder traversal = sorted order!

Ràng buộc này cho phép tìm kiếm nhanh — mỗi bước loại bỏ nửa cây, giống Binary Search trên mảng đã sắp xếp.

4 Traversals — Cách "thăm" mọi node ​

Với cây BST phía trên, thứ tự thăm node thay đổi tuỳ chiến lược:

TraversalThứ tựKết quả
InorderLeft → Root → Right5, 10, 12, 15, 18, 20, 25 (sorted! ✅)
PreorderRoot → Left → Right15, 10, 5, 12, 20, 18, 25
PostorderLeft → Right → Root5, 12, 10, 18, 25, 20, 15
Level-orderBFS theo tầng15, 10, 20, 5, 12, 18, 25

💡 Mẹo nhớ

Inorder = kết quả in sorted order (với BST). Preorder = root đi trước. Postorder = root đi sau.

Recursive Inorder ​

python
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.val)    # Process tại đây
    inorder(node.right)
cpp
void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->val << " ";   // Process tại đây
    inorder(node->right);
}
java
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    System.out.print(node.val + " ");  // Process tại đây
    inorder(node.right);
}

Iterative Inorder (Stack) — Bắt buộc biết cho phỏng vấn! ​

Recursive dễ viết, nhưng interviewer thường yêu cầu iterative để test hiểu biết về stack:

python
def inorder_iterative(root):
    stack, result = [], []
    curr = root
    while curr or stack:
        while curr:           # Đi sâu nhất bên trái
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()    # Backtrack
        result.append(curr.val)
        curr = curr.right     # Chuyển sang phải
    return result
cpp
vector<int> inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    vector<int> result;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top(); stk.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}
java
List<Integer> inorderIterative(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

BST Operations — Độ phức tạp ​

Thao tácAverageWorst (degenerate)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
Inorder traversalO(n)O(n)

Degenerate Tree — Tại sao cần cân bằng ​

Nếu bạn insert 1, 2, 3, 4, 5 theo thứ tự tăng dần vào BST:

Degenerate BST:
  [1]
    \
    [2]
      \
      [3]
        \
        [4]
          \
          [5]    ← Đây literally là một linked list!

Mọi thao tác trở thành O(n) — mất hoàn toàn lợi thế BST. Đây là lý do cần cây cân bằng (AVL Tree, Red-Black Tree) để đảm bảo height luôn O(log n).

⚠️ Phỏng vấn thường hỏi

"Worst-case complexity của BST search là bao nhiêu?" → O(n), khi cây degenerate. Đừng vội nói O(log n) — đó chỉ là average case trên cây cân bằng.

Visualizer States — Binary Tree ​

VISUALIZER STATES — Binary Tree:
State 1: VISIT      — current node highlights in yellow
State 2: GO_LEFT    — arrow animates to left child
State 3: GO_RIGHT   — arrow animates to right child
State 4: PROCESS    — node turns green (visited/processed)
State 5: BACKTRACK  — return to parent (dashed line)

Phần 2 — Heap ​

Heap là gì? ​

Heap là một complete binary tree thoả mãn heap property:

  • Max-heap: parent ≥ children → root = maximum
  • Min-heap: parent ≤ children → root = minimum

Điểm đặc biệt: heap được lưu trong array — không cần pointer như tree thông thường.

Heap as Array — Ánh xạ trực quan ​

Max Heap (tree view):
              [90]
             /    \
          [70]    [80]
          /  \    /  \
       [30] [50] [60] [40]

Array representation (0-indexed):
Index:  0   1   2   3   4   5   6
Value: 90  70  80  30  50  60  40

Navigation formulas:
  Parent(i)     = (i - 1) / 2     (integer division)
  LeftChild(i)  = 2*i + 1
  RightChild(i) = 2*i + 2

💡 Tại sao dùng array?

Complete binary tree không có "lỗ hổng" — mọi level đều đầy (trừ level cuối, lấp từ trái sang phải). Vì vậy array biểu diễn hoàn hảo mà không waste memory cho pointer.

Swim (Sift Up) & Sink (Sift Down) ​

Swim — sau khi insert ở cuối: so sánh với parent, swap lên nếu vi phạm heap property. Sink — sau khi extract root: đặt phần tử cuối lên root, swap xuống với con lớn/nhỏ hơn.

python
def swim(heap, i):
    """Sift up: dùng sau insert."""
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:   # Max-heap
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

def sink(heap, i, size):
    """Sift down: dùng sau extract root."""
    while 2 * i + 1 < size:
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < size and heap[left] > heap[largest]:
            largest = left
        if right < size and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest
cpp
void swim(vector<int>& heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] > heap[parent]) {
            swap(heap[i], heap[parent]);
            i = parent;
        } else break;
    }
}

void sink(vector<int>& heap, int i, int size) {
    while (2 * i + 1 < size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < size && heap[left] > heap[largest])
            largest = left;
        if (right < size && heap[right] > heap[largest])
            largest = right;
        if (largest == i) break;
        swap(heap[i], heap[largest]);
        i = largest;
    }
}
java
void swim(int[] heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] > heap[parent]) {
            int tmp = heap[i]; heap[i] = heap[parent]; heap[parent] = tmp;
            i = parent;
        } else break;
    }
}

void sink(int[] heap, int i, int size) {
    while (2 * i + 1 < size) {
        int left = 2 * i + 1, right = 2 * i + 2, largest = i;
        if (left < size && heap[left] > heap[largest]) largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;
        int tmp = heap[i]; heap[i] = heap[largest]; heap[largest] = tmp;
        i = largest;
    }
}

TẠI SAO heapify là O(n), KHÔNG PHẢI O(n log n) ​

Đây là câu hỏi kinh điển trong phỏng vấn. Hầu hết mọi người nghĩ: build heap = n lần insert, mỗi insert O(log n) → O(n log n). Sai!

Bottom-up heapify bắt đầu từ node cuối cùng không phải leaf, gọi sink cho mỗi node:

Phân tích số swap tối đa tại mỗi tầng:
- Leaves    (n/2 nodes): 0 swaps mỗi node    → tổng = 0
- Tầng trên (n/4 nodes): tối đa 1 swap       → tổng = n/4
- Tầng trên (n/8 nodes): tối đa 2 swaps      → tổng = 2n/8
- Tầng trên (n/16 nodes): tối đa 3 swaps     → tổng = 3n/16
- ...
- Root       (1 node):    tối đa log n swaps  → tổng = log n

Tổng = n/4 × 1 + n/8 × 2 + n/16 × 3 + ...
     = n × Σ(k / 2^(k+1))  với k = 1 .. log n
     = n × (hằng số ≈ 2)
     = O(n) ✅

Trực giác: phần lớn node nằm ở tầng dưới (gần leaf) và chỉ cần rất ít swap. Chỉ root mới cần log n swap, nhưng chỉ có 1 root.

python
def heapify(arr):
    """Build max-heap in O(n) — bottom-up."""
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):  # Từ node cuối có con → root
        sink(arr, i, n)
cpp
void heapify(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        sink(arr, i, n);
    }
}
java
void heapify(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        sink(arr, i, n);
    }
}

💡 HPN Pro Tip

Trong phỏng vấn, nếu interviewer hỏi "build heap complexity?", trả lời "O(n) with bottom-up heapify" ngay lập tức thể hiện bạn hiểu sâu hơn average candidate. Đa số sẽ nói O(n log n) — đó là cách top-down, không tối ưu.

Priority Queue — The Abstraction ​

Heap là cấu trúc dữ liệu cụ thể. Priority Queue là interface trừu tượng:

OperationPriority Queue (interface)Heap (implementation)
Insertpq.push(priority, value)swim — O(log n)
Extractpq.pop() → phần tử ưu tiên nhấtsink — O(log n)
Peekpq.top() → xem không xoáTrả arr[0] — O(1)

Ứng dụng: Dijkstra's algorithm, Huffman coding, OS process scheduler, merge K sorted lists (bài phỏng vấn kinh điển).

Visualizer States — Heap ​

VISUALIZER STATES — Heap:
State 1: INSERT     — new element appears at bottom-right
State 2: SWIM_UP    — element compared with parent, swap upward
State 3: EXTRACT    — root removed, last element moves to root
State 4: SINK_DOWN  — element compared with children, swap down
State 5: HEAP_VALID — all nodes satisfy heap property (green)

Phần 3 — Graph ​

Bức tranh tư duy ​

Graph là cấu trúc tổng quát nhất — một tập vertices (đỉnh) nối bởi edges (cạnh). Tree thực chất là graph đặc biệt (connected, acyclic). Mạng xã hội, bản đồ giao thông, internet — tất cả đều là graph.

Graph Vocabulary ​

Thuật ngữÝ nghĩaVí dụ
Vertex (V)Đỉnh / nodeThành phố, user, trang web
Edge (E)Cạnh nối 2 vertexĐường bay, friendship, hyperlink
DirectedCạnh có hướng (A → B ≠ B → A)Twitter follow, one-way street
UndirectedCạnh vô hướng (A — B = B — A)Facebook friendship, two-way road
WeightedCạnh có trọng sốKhoảng cách, chi phí, latency
DegreeSố cạnh nối với 1 vertexIn-degree, out-degree (directed)
PathDãy vertex nối liền nhauA → C → D → B
CyclePath quay về vertex xuất phátA → B → C → A
Connected componentNhóm vertex liên thông với nhau"Đảo" riêng trong graph

Minh hoạ ASCII ​

Undirected Graph:          Directed Weighted Graph:
    A --- B                    A --5--> B
    |   / |                    |        |
    |  /  |                    3        2
    | /   |                    |        |
    C --- D                    v        v
                               C --1--> D

Adjacency List vs Adjacency Matrix ​

Hai cách phổ biến nhất để biểu diễn graph trong code:

Adjacency List ​

A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C]

Adjacency Matrix ​

    A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 1 ]
C [ 1, 1, 0, 1 ]
D [ 0, 1, 1, 0 ]

So sánh chi tiết ​

Tiêu chíAdjacency ListAdjacency Matrix
SpaceO(V + E) ✅O(V²)
Edge lookup "A nối B?"O(degree)O(1) ✅
Iterate neighborsO(degree) ✅O(V)
Add edgeO(1) ✅O(1) ✅
Dense graph (E ≈ V²)Dùng đượcTốt hơn ✅
Sparse graph (E ≪ V²)Tốt hơn ✅Waste memory

💡 HPN Pro Tip

90% bài phỏng vấn dùng adjacency list vì graph thường sparse. Chỉ dùng matrix khi graph dense HOẶC cần check edge existence O(1) thường xuyên.

Code — Xây adjacency list từ edge list ​

python
from collections import defaultdict

def build_graph(edges):
    """Build undirected adjacency list from edge list."""
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)   # Bỏ dòng này nếu directed
    return graph

# Ví dụ
edges = [("A","B"), ("A","C"), ("B","C"), ("B","D"), ("C","D")]
g = build_graph(edges)
# g = {'A': ['B','C'], 'B': ['A','C','D'], 'C': ['A','B','D'], 'D': ['B','C']}
cpp
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

unordered_map<string, vector<string>> buildGraph(
    vector<pair<string,string>>& edges
) {
    unordered_map<string, vector<string>> graph;
    for (auto& [u, v] : edges) {
        graph[u].push_back(v);
        graph[v].push_back(u);  // Bỏ dòng này nếu directed
    }
    return graph;
}
java
import java.util.*;

Map<String, List<String>> buildGraph(String[][] edges) {
    Map<String, List<String>> graph = new HashMap<>();
    for (String[] e : edges) {
        graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        graph.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]); // undirected
    }
    return graph;
}

💡 Weighted Graph

Khi cạnh có trọng số, lưu tuple (neighbor, weight) thay vì chỉ neighbor. Ví dụ Python: graph[u].append((v, weight)). Cách này dùng trực tiếp cho Dijkstra ở bài tiếp theo.

Visualizer States — Graph ​

VISUALIZER STATES — Graph:
State 1: ADD_VERTEX       — new node appears with fade-in
State 2: ADD_EDGE         — line draws between two nodes
State 3: HIGHLIGHT_NEIGHBORS — all neighbors of selected node glow
State 4: WEIGHT_LABEL     — edge weight appears on hover

Practice ​

🧠 Quiz ​

🧠 Quiz

Câu 1: Inorder traversal của BST cho kết quả gì? ​

  • [ ] A) Sorted descending
  • [x] B) Sorted ascending
  • [ ] C) Level-order
  • [ ] D) Random order

💡 Giải thích: Inorder (Left → Root → Right) trên BST luôn cho kết quả sorted ascending vì mọi giá trị bên trái < root < bên phải. Đây là tính chất cực kỳ quan trọng cần nhớ.

Câu 2: Build heap (heapify) có độ phức tạp bao nhiêu? ​

  • [ ] A) O(n²)
  • [ ] B) O(n log n)
  • [x] C) O(n)
  • [ ] D) O(log n)

💡 Giải thích: Bottom-up heapify là O(n) vì phần lớn node ở tầng dưới (gần leaf) chỉ cần rất ít swap. Tổng công việc = n × Σ(k/2^(k+1)) ≈ 2n = O(n). Đây là câu mà nhiều candidate trả lời sai thành O(n log n).

Câu 3: Khi nào nên dùng adjacency matrix thay vì adjacency list? ​

  • [ ] A) Graph có ít cạnh (sparse)
  • [x] B) Graph có nhiều cạnh (dense) hoặc cần check edge O(1)
  • [ ] C) Luôn luôn dùng matrix vì nhanh hơn
  • [ ] D) Khi graph có trọng số

💡 Giải thích: Adjacency matrix tốn O(V²) space nhưng cho edge lookup O(1). Chỉ đáng dùng khi graph dense (E ≈ V²) hoặc bạn cần kiểm tra "A nối B?" rất thường xuyên. Graph có trọng số dùng được cả hai cách.

Câu 4: Worst-case search trên BST (không cân bằng) là bao nhiêu? ​

  • [ ] A) O(1)
  • [ ] B) O(log n)
  • [x] C) O(n)
  • [ ] D) O(n log n)

💡 Giải thích: Khi BST degenerate (insert dữ liệu đã sorted), cây trở thành linked list → search phải duyệt tất cả n node → O(n). Đây là lý do cần AVL / Red-Black Tree.

🐛 Spot the Bug ​

Hàm BST insert dưới đây có lỗi logic — bạn tìm được không?

python
def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:  # ← BUG ở đây!
        root.right = insert(root.right, val)
    return root
💡 Gợi ý

Điều gì xảy ra khi val == root.val? Hàm có nên insert duplicate không?

✅ Lời giải

Dòng else: nên là elif val > root.val: để bỏ qua duplicate:

python
def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:   # ✅ FIX: skip duplicates
        root.right = insert(root.right, val)
    # val == root.val → do nothing (skip duplicate)
    return root

Phân tích: Với else, khi val == root.val, giá trị duplicate bị insert vào right subtree — vi phạm BST property "right > parent". Tuỳ yêu cầu, bạn có thể skip duplicate hoặc tăng counter, nhưng không bao giờ insert duplicate sang right mà không xử lý.

🧩 Parsons Problem — Build Adjacency List ​

Sắp xếp các dòng code để tạo adjacency list cho undirected graph:

Các dòng bị xáo trộn:

A: graph = defaultdict(list)
B: for u, v in edges:
C: graph[u].append(v)
D: graph[v].append(u)  # undirected
E: return graph
F: def build_graph(edges):
✅ Thứ tự đúng

F → A → B → C → D → E

python
def build_graph(edges):          # F
    graph = defaultdict(list)    # A
    for u, v in edges:           # B
        graph[u].append(v)       # C
        graph[v].append(u)       # D — undirected
    return graph                 # E

Giải thích: Định nghĩa hàm (F) → khởi tạo dict (A) → loop qua edges (B) → thêm cạnh hai chiều (C, D) → trả kết quả (E).

Tổng kết ​

✅ Checklist triển khai

Bạn đã nắm vững khi:

  • [ ] Vẽ được Binary Tree và chỉ ra root, leaf, height, depth
  • [ ] Thực hiện được 4 traversals (inorder, preorder, postorder, level-order) — cả recursive và iterative
  • [ ] Giải thích BST property và nhận ra degenerate tree = O(n)
  • [ ] Biết heap lưu trong array với formulas parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2
  • [ ] Trình bày được tại sao heapify là O(n) — bằng chứng minh tổng swap
  • [ ] Phân biệt được khi nào dùng adjacency list vs matrix
  • [ ] Xây dựng adjacency list từ edge list trong ngôn ngữ bạn chọn
  • [ ] Sẵn sàng học BFS, DFS, Dijkstra ở bài tiếp theo

📚 Bài liên quan

Đọc thêm:

📍 Trang tiếp theo ​

Bạn đã nắm vững ba cấu trúc phi tuyến nền tảng. Bài tiếp theo sẽ khai thác chúng — duyệt graph bằng BFS, DFS và tìm đường ngắn nhất bằng Dijkstra.

👉 Graph Traversals — BFS, DFS & Dijkstra

Professional Engineering Standards | © 2025 HPN Corporation