This programming guide is only available in Vietnamese. Switch to Vietnamese to read the full article.

Chào mừng bạn đến với bài học tổng kết cuối cùng của chuỗi tự học C++ - một bài học Capstone Project tích hợp toàn bộ kiến thức OOP, quản lý con trỏ, cấu trúc dữ liệu nâng cao, và lập trình ứng dụng tương tác trên web. Trong bài viết này, chúng ta sẽ:

  • Xây dựng Cây tìm kiếm nhị phân (BST) hoàn chỉnh với các phép toán Insert, Delete, Search và Traversal
  • Tìm hiểu sâu về Cây AVL tự cân bằng (Self-Balancing Trees) với các phép quay (Rotations)
  • Khám phá kiến trúc Visualizer Canvas - cách vẽ cây lên màn hình và tương tác real-time
  • Áp dụng Design Patterns (Observer, Strategy, MVC) vào dự án thực tế
  • Tìm hiểu các cấu trúc dữ liệu nâng cao khác và ứng dụng trong công nghệ hiện đại

1. Định nghĩa & Tính chất Cây tìm kiếm nhị phân (BST)

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một cấu trúc dữ liệu phân cấp dạng cây nhị phân có các ràng buộc:

  • Cấu trúc nhị phân: Mỗi nút tối đa có 2 nút con (con trái và con phải)
  • Ràng buộc giá trị: Với bất kỳ nút nào:
    • Tất cả giá trị ở cây con trái < giá trị của nút cha
    • Tất cả giá trị ở cây con phải > giá trị của nút cha
  • Tính chất đệ quy: Cây con trái và cây con phải của mỗi nút cũng phải là BST hợp lệ

Nhờ quy luật phân cấp này, việc tìm kiếm trên cây cân bằng chỉ tốn độ phức tạp trung bình là O(log n) - nhanh hơn linear search O(n) rất nhiều. Tuy nhiên, nếu cây bị mất cân bằng (ví dụ chỉ có nhánh trái liên tiếp), độ phức tạp có thể suy giảm thành O(n).

2. Thiết kế BST bằng C++ OOP

Để xây dựng BST trong C++, chúng ta cần:

  • Lớp Node đại diện cho từng nút với giá trị và con trỏ đến nút con
  • Lớp BST chứa gốc cây (root) và các phương thức công khai (public methods)
  • Các phương thức riêng (private methods) để thực hiện thuật toán đệ quy
bst_node.h - Cấu trúc Node 
struct BSTNode {
    int value;
    BSTNode* left;
    BSTNode* right;
    int height;  // Dung cho AVL trees sau nay

    BSTNode(int val)
        : value(val), left(nullptr), right(nullptr), height(1) {}
};
bst.h - Khai báo lớp BST 
#include <iostream>
#include <queue>
#include <vector>

class BST {
private:
    BSTNode* root;

    // Private recursive methods
    BSTNode* insertNode(BSTNode* node, int value);
    BSTNode* searchNode(BSTNode* node, int value);
    BSTNode* deleteNode(BSTNode* node, int value);
    BSTNode* findMin(BSTNode* node);
    void inOrderTraversal(BSTNode* node, std::vector<int>& result);
    void deleteTree(BSTNode* node);

public:
    BST() : root(nullptr) {}
    ~BST() { deleteTree(root); }

    // Public interface
    void insert(int value);
    bool search(int value);
    void deleteValue(int value);
    std::vector<int> getInOrder();
    void print();
};

3. Thuật toán BST: Insert, Delete, Search - Deep Dive

Đây là phần lõi của BST. Chúng ta sẽ tìm hiểu chi tiết từng phép toán và các trường hợp đặc biệt.

3.1 Phép Insert (Chèn)

Khi chèn một giá trị mới vào BST, chúng ta luôn chèn ở lá cây. Quá trình đơn giản:

  1. Nếu cây rỗng, tạo nút mới làm gốc
  2. Nếu giá trị mới < giá trị nút hiện tại, đi sang trái
  3. Nếu giá trị mới > giá trị nút hiện tại, đi sang phải
  4. Nếu giá trị mới == giá trị nút hiện tại, tùy chọn (chấp nhận hay từ chối trùng lặp)
  5. Tiếp tục đệ quy cho đến khi tìm được vị trí lá
bst.cpp - Insert Implementation 
BSTNode* BST::insertNode(BSTNode* node, int value) {
    // Base case: Found the position for new node
    if (node == nullptr) {
        return new BSTNode(value);
    }

    // Recursive case: Navigate left or right
    if (value < node->value) {
        node->left = insertNode(node->left, value);
    }
    else if (value > node->value) {
        node->right = insertNode(node->right, value);
    }
    // If value == node->value, duplicate detected
    // Option: Ignore duplicates or increment a counter

    return node;
}

void BST::insert(int value) {
    root = insertNode(root, value);
}

Độ phức tạp Insert: O(log n) trung bình (cây cân bằng), O(n) trường hợp xấu (cây suy biến)

3.2 Phép Search (Tìm kiếm)

Tìm kiếm giá trị trong BST lợi dụng tính chất sắp xếp: giảm nửa không gian tìm kiếm mỗi lần so sánh.

bst.cpp - Search Implementation 
BSTNode* BST::searchNode(BSTNode* node, int value) {
    // Base case: Node not found or tree is empty
    if (node == nullptr) {
        return nullptr;
    }

    // Check current node
    if (value == node->value) {
        return node;  // Found!
    }

    // Navigate based on BST property
    if (value < node->value) {
        return searchNode(node->left, value);
    } else {
        return searchNode(node->right, value);
    }
}

bool BST::search(int value) {
    return searchNode(root, value) != nullptr;
}

Độ phức tạp Search: O(log n) trung bình, O(n) trường hợp xấu

3.3 Phép Delete (Xóa) - Trường hợp khó nhất

Delete là phép toán phức tạp nhất vì cần xử lý 3 trường hợp:

  1. Nút lá (No children): Xóa trực tiếp, gán con trỏ cha thành nullptr
  2. Nút có 1 con: Thay thế nút bằng con duy nhất của nó
  3. Nút có 2 con: Tìm nút thay thế (Inorder Successor hoặc Inorder Predecessor)

Inorder Successor: Nút nhỏ nhất trong cây con phải (đi phải 1 lần, sau đó đi trái liên tiếp)

Inorder Predecessor: Nút lớn nhất trong cây con trái (đi trái 1 lần, sau đó đi phải liên tiếp)

bst.cpp - Delete Implementation 
BSTNode* BST::findMin(BSTNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

BSTNode* BST::deleteNode(BSTNode* node, int value) {
    if (node == nullptr) return nullptr;

    // Navigate to the node to delete
    if (value < node->value) {
        node->left = deleteNode(node->left, value);
    }
    else if (value > node->value) {
        node->right = deleteNode(node->right, value);
    }
    else {
        // Found the node to delete

        // Case 1: No children (leaf node)
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            return nullptr;
        }

        // Case 2: One child
        if (node->left == nullptr) {
            BSTNode* temp = node->right;
            delete node;
            return temp;
        }
        if (node->right == nullptr) {
            BSTNode* temp = node->left;
            delete node;
            return temp;
        }

        // Case 3: Two children
        // Use Inorder Successor (smallest in right subtree)
        BSTNode* successor = findMin(node->right);
        node->value = successor->value;  // Copy value
        node->right = deleteNode(node->right, successor->value);
    }

    return node;
}

Độ phức tạp Delete: O(log n) trung bình, O(n) trường hợp xấu

Tóm tắt độ phức tạp BST:

Phép toán Trường hợp tốt Trường hợp xấu Cây cân bằng (Avg)
Insert O(log n) O(n) O(log n)
Search O(log n) O(n) O(log n)
Delete O(log n) O(n) O(log n)
In-Order Traversal O(n) O(n) O(n)

4. Cây AVL & Cấu trúc tự cân bằng (Self-Balancing Trees)

BST thường có khuyết điểm: nếu bạn chèn dữ liệu đã được sắp xếp (ví dụ: 1, 2, 3, 4, 5), cây sẽ suy biến thành một linked list tuyến tính, mất đi ưu thế độ phức tạp logarithm. Cây AVL (Adelson-Velsky-Landis) giải quyết bài toán này bằng cách tự động cân bằng cây sau mỗi phép insert/delete.

4.1 Khái niệm Balance Factor & Rotations

Trong cây AVL, Balance Factor (BF) của một nút = chiều cao cây con trái - chiều cao cây con phải.

  • Nếu BF = -1, 0, hay 1 → Cây cân bằng
  • Nếu BF < -1 hoặc BF > 1 → Cây mất cân bằng, cần quay (rotation)

Có 4 loại quay:

avl_rotations.txt - Minh hoạ Rotations 
1. LEFT ROTATION (Quay trái - khi cây con phải nặng)

   Trước:              Sau:
     x                   y
      \                 / \
       y       -->      x   z
        \
         z

2. RIGHT ROTATION (Quay phải - khi cây con trái nặng)

   Trước:              Sau:
       x               y
      /               / \
     y        -->     z   x
    /
   z

3. LEFT-RIGHT ROTATION (Quay trái-phải)
   - Trước tiên quay trái nút con trái
   - Sau đó quay phải nút cha
   - Dùng khi: BF > 1 và con trái có BF < 0

4. RIGHT-LEFT ROTATION (Quay phải-trái)
   - Trước tiên quay phải nút con phải
   - Sau đó quay trái nút cha
   - Dùng khi: BF < -1 và con phải có BF > 0
avl.cpp - AVL Rotation Implementation 
int getHeight(AVLNode* node) {
    return node == nullptr ? 0 : node->height;
}

int getBalance(AVLNode* node) {
    return node == nullptr ? 0 : getHeight(node->left) - getHeight(node->right);
}

// Left Rotation
AVLNode* rotateLeft(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* temp = y->left;

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

    x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
    y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));

    return y;
}

// Right Rotation
AVLNode* rotateRight(AVLNode* x) {
    AVLNode* y = x->left;
    AVLNode* temp = y->right;

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

    x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
    y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));

    return y;
}

// Insert with Balancing
AVLNode* insertAVL(AVLNode* node, int value) {
    // Standard BST insertion
    if (node == nullptr) {
        return new AVLNode(value);
    }

    if (value < node->value) {
        node->left = insertAVL(node->left, value);
    } else if (value > node->value) {
        node->right = insertAVL(node->right, value);
    } else {
        return node;  // Duplicate
    }

    // Update height
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));

    // Get balance factor and rebalance if needed
    int balance = getBalance(node);

    // Left Heavy
    if (balance > 1) {
        if (getBalance(node->left) < 0) {
            node->left = rotateLeft(node->left);  // Left-Right case
        }
        return rotateRight(node);  // Left-Left case
    }

    // Right Heavy
    if (balance < -1) {
        if (getBalance(node->right) > 0) {
            node->right = rotateRight(node->right);  // Right-Left case
        }
        return rotateLeft(node);  // Right-Right case
    }

    return node;
}

Lợi thế của AVL Trees:

  • Luôn duy trì độ cao logarithmic O(log n)
  • Tất cả phép toán (insert, search, delete) đều O(log n) đảm bảo
  • Hữu ích trong hệ thống real-time cần response time dự đoán được

Nhược điểm:

  • Cần thêm logic rotation sau mỗi insert/delete phức tạp hơn BST
  • Chi phí rebalance có thể cao với dữ liệu thay đổi liên tục
  • Red-Black trees có thể tốt hơn khi insert/delete thường xuyên

5. Kiến trúc Canvas Visualizer

Để trực quan hóa cây trên màn hình, chúng ta cần:

  1. Tính toán vị trí (x, y) của mỗi nút trên canvas
  2. Vẽ nút (hình tròn) và cạnh (đường nối)
  3. Xử lý sự kiện người dùng (click, drag, input)
  4. Cập nhật trực quan khi tree thay đổi

5.1 Thuật toán định vị nút: In-order Positioning

Cách hiệu quả nhất để định vị nút là sử dụng In-order Traversal. Chúng ta duyệt cây theo thứ tự Trái-Cha-Phải, gán tọa độ x theo số hiệu, y theo độ sâu:

visualizer.js - Node Positioning Algorithm 
class TreeVisualizer {
    constructor(canvasId) {
        this.canvas = document.getElementById(canvasId);
        this.ctx = this.canvas.getContext('2d');
        this.nodeRadius = 25;
        this.nodePositions = new Map();
        this.counter = 0;
    }

    // In-order traversal to assign x-coordinates
    assignPositions(node, depth, minX, maxX) {
        if (!node) return;

        const midX = (minX + maxX) / 2;
        const y = 60 + depth * 80;  // Depth determines y-coordinate

        // Recursively position left subtree
        this.assignPositions(node.left, depth + 1, minX, midX);

        // Position current node
        this.nodePositions.set(node.id, {
            x: midX,
            y: y,
            value: node.value
        });

        // Recursively position right subtree
        this.assignPositions(node.right, depth + 1, midX, maxX);
    }

    // Draw tree on canvas
    draw(root) {
        this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
        this.nodePositions.clear();

        // Calculate positions
        this.assignPositions(root, 0, 50, this.canvas.width - 50);

        // Draw edges first (so nodes appear on top)
        this.drawEdges(root);

        // Then draw nodes
        this.drawNodes(root);
    }

    drawEdges(node) {
        if (!node) return;

        const parentPos = this.nodePositions.get(node.id);
        if (!parentPos) return;

        if (node.left) {
            const childPos = this.nodePositions.get(node.left.id);
            if (childPos) {
                this.ctx.strokeStyle = 'rgba(255,255,255,0.2)';
                this.ctx.lineWidth = 2;
                this.ctx.beginPath();
                this.ctx.moveTo(parentPos.x, parentPos.y);
                this.ctx.lineTo(childPos.x, childPos.y);
                this.ctx.stroke();
            }
            this.drawEdges(node.left);
        }

        if (node.right) {
            const childPos = this.nodePositions.get(node.right.id);
            if (childPos) {
                this.ctx.strokeStyle = 'rgba(255,255,255,0.2)';
                this.ctx.lineWidth = 2;
                this.ctx.beginPath();
                this.ctx.moveTo(parentPos.x, parentPos.y);
                this.ctx.lineTo(childPos.x, childPos.y);
                this.ctx.stroke();
            }
            this.drawEdges(node.right);
        }
    }

    drawNodes(node) {
        if (!node) return;

        const pos = this.nodePositions.get(node.id);
        if (!pos) return;

        // Draw node circle
        this.ctx.fillStyle = 'rgba(59, 130, 246, 0.8)';
        this.ctx.beginPath();
        this.ctx.arc(pos.x, pos.y, this.nodeRadius, 0, 2 * Math.PI);
        this.ctx.fill();

        // Draw value text
        this.ctx.fillStyle = '#fff';
        this.ctx.font = 'bold 14px Arial';
        this.ctx.textAlign = 'center';
        this.ctx.textBaseline = 'middle';
        this.ctx.fillText(pos.value, pos.x, pos.y);

        // Recursively draw children
        if (node.left) this.drawNodes(node.left);
        if (node.right) this.drawNodes(node.right);
    }
}

5.2 Xử lý tương tác người dùng

Tương tác bao gồm nhập giá trị, thêm node, xóa node, tìm kiếm và highlight:

visualizer.js - Event Handling 
// Setup event listeners
setupEventListeners() {
    const inputField = document.getElementById('valueInput');
    const addBtn = document.getElementById('addBtn');
    const deleteBtn = document.getElementById('deleteBtn');
    const searchBtn = document.getElementById('searchBtn');

    addBtn.addEventListener('click', () => {
        const value = parseInt(inputField.value);
        if (!isNaN(value) && value >= 1 && value <= 999) {
            this.tree.insert(value);
            this.draw(this.tree.root);
            inputField.value = '';
            inputField.focus();
        }
    });

    deleteBtn.addEventListener('click', () => {
        const value = parseInt(inputField.value);
        if (!isNaN(value)) {
            this.tree.deleteValue(value);
            this.draw(this.tree.root);
            inputField.value = '';
        }
    });

    searchBtn.addEventListener('click', () => {
        const value = parseInt(inputField.value);
        if (!isNaN(value)) {
            const found = this.tree.search(value);
            this.highlightNode(value, found);
        }
    });

    // Enter key support
    inputField.addEventListener('keypress', (e) => {
        if (e.key === 'Enter') addBtn.click();
    });
}

// Highlight found node
highlightNode(value, found) {
    if (found) {
        // Find and highlight the node in our visualization
        for (let [nodeId, pos] of this.nodePositions) {
            if (pos.value === value) {
                // Draw highlight effect
                this.ctx.strokeStyle = '#10b981';
                this.ctx.lineWidth = 3;
                this.ctx.beginPath();
                this.ctx.arc(pos.x, pos.y, this.nodeRadius + 5, 0, 2 * Math.PI);
                this.ctx.stroke();
                break;
            }
        }
    }
}

6. Design Patterns trong Visualizer

Một dự án chuyên nghiệp cần sử dụng các design patterns để tổ chức code sạch và dễ bảo trì:

6.1 Observer Pattern: Cập nhật UI khi Tree thay đổi

Khi tree thay đổi (insert/delete), chúng ta cần thông báo cho tất cả observers (UI components) cập nhật:

bst.js - Observer Pattern 
class ObservableBST {
    constructor() {
        this.root = null;
        this.observers = [];
    }

    // Register observer
    subscribe(observer) {
        this.observers.push(observer);
    }

    // Notify all observers
    notifyObservers() {
        this.observers.forEach(observer => observer.update(this.root));
    }

    insert(value) {
        this.root = this._insertNode(this.root, value);
        this.notifyObservers();  // Notify UI to redraw
    }

    deleteValue(value) {
        this.root = this._deleteNode(this.root, value);
        this.notifyObservers();
    }

    // ... rest of tree methods
}

// Usage
const tree = new ObservableBST();
const visualizer = new TreeVisualizer('canvas');

tree.subscribe({
    update: (root) => {
        visualizer.draw(root);  // Auto-update when tree changes
    }
});

6.2 Strategy Pattern: Khác nhau loại Tree (BST vs AVL vs Red-Black)

Sử dụng Strategy pattern cho phép switch giữa các loại cây mà không thay đổi code của visualizer:

trees.js - Strategy Pattern 
// Abstract strategy
class TreeStrategy {
    insert(value) { throw new Error('Not implemented'); }
    delete(value) { throw new Error('Not implemented'); }
    search(value) { throw new Error('Not implemented'); }
    getRoot() { throw new Error('Not implemented'); }
}

// Concrete strategies
class BSTStrategy extends TreeStrategy {
    constructor() {
        super();
        this.tree = new BST();
    }

    insert(value) { this.tree.insert(value); }
    delete(value) { this.tree.deleteValue(value); }
    search(value) { return this.tree.search(value); }
    getRoot() { return this.tree.root; }
}

class AVLStrategy extends TreeStrategy {
    constructor() {
        super();
        this.tree = new AVLTree();
    }

    insert(value) { this.tree.insert(value); }
    delete(value) { this.tree.deleteValue(value); }
    search(value) { return this.tree.search(value); }
    getRoot() { return this.tree.root; }
}

// Usage - can switch strategies easily
class Application {
    setTreeStrategy(strategy) {
        this.treeStrategy = strategy;
    }

    addNode(value) {
        this.treeStrategy.insert(value);
        this.redraw();
    }
}

6.3 MVC Pattern: Model-View-Controller Separation

Model: BST/AVL tree logic | View: Canvas visualization | Controller: Event handling & coordination

  • Model: Lớp Tree chứa dữ liệu và logic, không biết gì về cách hiển thị
  • View: Lớp Visualizer chỉ vẽ, không chứa logic cây
  • Controller: Lớp Application điều phối giữa Model và View

7. Các cấu trúc dữ liệu nâng cao khác & Ứng dụng

7.1 Red-Black Trees

Như AVL nhưng ít rebalance hơn. Mỗi nút được tô màu đỏ hoặc đen với các ràng buộc:

  • Nút gốc luôn đen
  • Nút lá (NIL) là đen
  • Nút đỏ phải có con đen
  • Mọi đường từ nút đến lá có số lượng nút đen bằng nhau

Ưu điểm: Ít rotation hơn AVL, tốt cho insert/delete thường xuyên. Được dùng trong std::map, std::set của C++.

7.2 B-Trees

Được dùng trong database và file systems. Mỗi nút có thể chứa nhiều giá trị và con, tối ưu cho truy cập disk.

7.3 Trie Trees

Tối ưu cho autocomplete, spell checker, IP routing. Mỗi đường từ gốc đến lá tạo thành một từ.

7.4 Ứng dụng thực tế:

  • Cơ sở dữ liệu (Database): B-trees, B+ trees cho indexing
  • Hệ điều hành (OS): AVL/Red-Black trees cho memory management
  • Trình duyệt web: BST cho DOM tree, event handling
  • Game development: BSP (Binary Space Partition) trees cho collision detection
  • Machine Learning: Decision trees cho classification
  • Compiler design: Trie trees cho symbol table

8. Bộ mô phỏng tương tác BST Visualizer

Dưới đây là ứng dụng mô phỏng trực quan cây tìm kiếm nhị phân được dựng bằng HTML5 Canvas và JavaScript. Bạn hãy nhập các con số (từ 1 đến 999) và nhấn "Thêm Node" để nhìn thấy liên kết phân nhánh tự động dịch chuyển và vẽ đồ họa trực quan:

9. Tóm tắt Bài học & Khuyến nghị Tiếp tục Học

Qua bài tập tổng kết này, chúng ta đã áp dụng:

  • Lập trình hướng đối tượng OOP (Classes, Encapsulation)
  • Quản lý con trỏ và bộ nhớ Heap (new/delete)
  • Thuật toán đệ quy phức tạp (Insert, Delete, Search, Traversals)
  • Cấu trúc dữ liệu nâng cao (Self-balancing trees)
  • Lập trình ứng dụng web (HTML5 Canvas, JavaScript events)
  • Design patterns (Observer, Strategy, MVC)
  • Phân tích độ phức tạp thuật toán (Big O notation)

Hướng phát triển tiếp theo:

  • Nâng cấp: Thêm Red-Black tree, Splay tree implementations
  • Performance: Viết benchmark so sánh BST vs AVL vs Red-Black trên dataset khác nhau
  • Ứng dụng: Xây dựng database index system sử dụng B-trees
  • Web: Tạo interactive visualizer cho Trie, Segment tree, Fenwick tree
  • Competitive Programming: Sử dụng BST variants để giải các bài problem khó

Câu hỏi ôn tập kiến thức

Khi thực hiện delete nút có 2 con trong BST, ta sử dụng Inorder Successor. Tại sao lại chọn nút nhỏ nhất trong cây con phải, chứ không phải nút lớn nhất trong cây con trái?

A. Vì cây con phải luôn có giá trị lớn hơn.
B. Cả hai cách (Successor và Predecessor) đều hợp lệ, chỉ là quy ước chọn cái nào.
C. Vì nút đó không bao giờ có con phải.

Tải mã nguồn mẫu bài học

Bạn có thể tải file mã nguồn HTML mô phỏng Visualizer độc lập của bài học này để tự chạy trên máy tính hoặc chỉnh sửa tùy ý.

Tải bst_visualizer.html