Cấu Trúc Dữ Liệu Cây: Từ Gốc Đến Ngọn

20 phép so sánh thay vì 500.000

Một mảng một triệu phần tử chưa sắp xếp: tìm một giá trị bất kỳ tốn trung bình 500.000 phép so sánh. Vẫn một triệu phần tử đó, đặt trong cây tìm kiếm nhị phân cân bằng: tối đa 20 phép so sánh, vì $2^{20}$ vừa vượt qua một triệu.

Cây mua được khoảng cách đó bằng một ràng buộc rất chặt về hình dạng. Mất ràng buộc, cây suy biến thành danh sách liên kết và 20 phép so sánh quay về một triệu.

Cây tổng quát

Định nghĩa và tính chất

Cây nói về quan hệ. Gia phả là ví dụ gần nhất: bạn có cha mẹ, con cái, anh chị em, tổ tiên và hậu duệ. Khoa học máy tính mượn nguyên cấu trúc đó để tổ chức dữ liệu theo thứ bậc.

Định nghĩa: Cây T là tập các nút (node) lưu trữ phần tử, có quan hệ cha-con thoả: một nút gốc duy nhất không có cha, mọi nút khác có đúng một cha, có đúng một đường đi từ gốc tới bất kỳ nút nào, và không có chu trình.

Thuật ngữ:

Cây con (subtree): lấy một nút bất kỳ làm gốc rồi gom tất cả hậu duệ của nó lại, bạn được một cây con. Cây con cũng thoả đúng định nghĩa của cây: nó có gốc riêng, mọi nút trong nó vẫn có đúng một cha, vẫn không có chu trình. Nghĩa là mọi thuật toán viết cho cây đều chạy được nguyên xi trên cây con, và đó là lý do gần như mọi hàm xử lý cây đều viết bằng đệ quy: xử lý nút hiện tại, rồi gọi lại chính hàm đó cho từng cây con.

Nếu sơ đồ tổ chức dễ nhớ hơn: gốc là Chủ tịch công ty, mọi người cuối cùng đều báo cáo lên đó. Lá là thực tập sinh, không ai báo cáo cho họ. Nút trong là quản lý cấp trung, có cả cấp trên lẫn cấp dưới.

Hoặc gần hơn nữa: Chính phủ Trung ương (gốc) → Tỉnh/Thành phố → Quận/Huyện → Phường/Xã → Tổ dân phố (lá). Mỗi cấp là một mức độ sâu, tổng số cấp là chiều cao.

Ba tính chất mọi cây đều thoả:

• Cây N nút có đúng N-1 cạnh
• Giữa hai nút bất kỳ có đúng một đường đi
• Thêm cạnh nào cũng tạo chu trình; bỏ cạnh nào cũng làm cây đứt thành hai phần

Tính chất "đúng một đường đi" là thứ khiến việc tìm kiếm không bao giờ phải thử nhiều tuyến. Tính chất N-1 cạnh nói rằng cây là cách nối N nút lại với nhau bằng ít cạnh nhất có thể mà vẫn liên thông.

Kiểu dữ liệu trừu tượng cây (Tree ADT)

Tree ADT cho một giao diện chuẩn, giấu chi tiết cài đặt phía sau. Giống bảng điều khiển ô tô: không cần biết động cơ hoạt động ra sao vẫn lái được.

public interface Tree<E> extends Iterable<E> {
    // Phương thức điều hướng - tìm đường trong gia phả
    Position<E> root();                    // Ai là tổ tiên sáng lập?
    Position<E> parent(Position<E> p);     // Ai là cha mẹ của bạn?
    Iterable<Position<E>> children(Position<E> p);  // Ai là con của bạn?

    // Phương thức truy vấn - hỏi về các thành viên gia đình
    boolean isInternal(Position<E> p);     // Bạn có phải cha/mẹ không?
    boolean isExternal(Position<E> p);     // Bạn chưa có con đúng không ?
    boolean isRoot(Position<E> p);         // Bạn có phải cụ tổ không?

    // Phương thức tiện ích
    int size();                            // Gia tộc có bao nhiêu người?
    boolean isEmpty();                     // Đây là câu hỏi năm 1442 Hoàng hậu Nguyễn Thị Anh hỏi gia đình Nguyễn Trãi
    int numChildren(Position<E> p);        // Bạn có bao nhiêu con?
}

Interface Position đại diện cho một nút mà không để lộ cấu trúc bên trong.

Hiểu sâu về Position

Position là một hộp đen: bạn biết nó chứa dữ liệu, không biết nó nối với ai.

Ví dụ: sổ hộ khẩu

// Sổ hộ khẩu chỉ cho phép xem tên, không cho xem thông tin riêng tư khác
public interface FamilyMemberCard {
    String getName();  // Chỉ được xem tên
}

// Thực tế mỗi thành viên có nhiều thông tin
class FamilyMember implements FamilyMemberCard {
    private String name;
    private String idNumber;        // Số CMND - ẩn
    private String medicalHistory;  // Lịch sử bệnh - ẩn
    private FamilyMember parent;    // Cha/mẹ - ẩn
    private List<FamilyMember> children; // Con cái - ẩn

    public String getName() {
        return name;
    }
}

Tương tự với Position trong Tree:

// Position chỉ cho phép lấy phần tử, ẩn mọi thứ khác
public interface Position<E> {
    E element() throws IllegalStateException;
}

// Node thực tế có nhiều thông tin về quan hệ gia đình
class TreeNode<E> implements Position<E> {
    private E data;
    private TreeNode<E> parent;    // Ẩn khỏi người dùng
    private TreeNode<E> left;      // Ẩn khỏi người dùng
    private TreeNode<E> right;     // Ẩn khỏi người dùng

    public E element() {
        return data;
    }
}

Tại sao cần Position?

// KHÔNG TỐT - Người ngoài có thể phá vỡ cấu trúc của cây
TreeNode<String> member = familyTree.getNode(1); // Lấy nút thành viên
member.parent = null;  // Nguy hiểm! Phá hỏng cấu trúc của cây

// TỐT - Người ngoài chỉ xem được tên
Position<String> pos = familyTree.getPosition(1); // Lấy vị trí thành viên
String name = pos.element();  // An toàn
// pos.parent = null;  // Không thể! Position không có parent/children

Position là cửa sổ nhỏ chỉ nhìn thấy dữ liệu của nút, không chạm được vào các liên kết.

Chỗ dùng thật: chuỗi bình luận trả lời nhau trên diễn đàn hay mạng xã hội là một cây. Bài đăng là gốc, bình luận trực tiếp là con của gốc, mỗi câu trả lời mở một cây con. Cấu trúc này cho phép hiển thị hội thoại theo luồng mà không phải quét lại toàn bộ bình luận để biết cái nào trả lời cái nào.

Cây nhị phân

Kiểu dữ liệu trừu tượng cây nhị phân

Cây nhị phân giới hạn mỗi nút tối đa hai con. Ràng buộc này nhỏ nhưng đủ để mọi phép toán trên cây có một dạng đệ quy gọn, và là nền của heap, cây tìm kiếm nhị phân, cây quyết định.

graph TD;
    A[Root] --> B[Left Child]
    A --> C[Right Child]
    B --> D[Left Grandchild]
    B --> E[Right Grandchild]
    C --> F[Left Grandchild]
    C --> G[Right Grandchild]
    style A fill:#f9f,stroke:#333,stroke-width:4px
    style B fill:#bbf,stroke:#333,stroke-width:2px
    style C fill:#bbf,stroke:#333,stroke-width:2px
    style D fill:#ddf,stroke:#333,stroke-width:1px
    style E fill:#ddf,stroke:#333,stroke-width:1px
    style F fill:#ddf,stroke:#333,stroke-width:1px
    style G fill:#ddf,stroke:#333,stroke-width:1px

BinaryTree ADT mở rộng Tree ADT:

public interface BinaryTree<E> extends Tree<E> {
    Position<E> left(Position<E> p);   // Con đầu lòng của bạn
    Position<E> right(Position<E> p);  // Con thứ hai của bạn
    Position<E> sibling(Position<E> p); // Anh chị em duy nhất có thể có
}

Tính chất của cây nhị phân

Vài con số nên thuộc lòng, vì chúng quyết định việc chọn loại cây:

• Số nút tối đa ở cấp i: $2^i$ (cấp 0 có 1, cấp 1 có 2, cấp 2 có 4...)
• Số nút tối đa trong cây cao h: $2^{h+1} - 1$
• Chiều cao tối thiểu cho N nút: $\lfloor \log_2 N \rfloor$

Các loại cây nhị phân đặc biệt:

• Đầy đủ (full): mỗi nút cha có đúng 0 hoặc 2 con, không có con đơn
• Hoàn chỉnh (complete): mọi tầng đều đầy, trừ tầng cuối; tầng cuối điền từ trái sang phải, không chừa khoảng trống ở giữa
• Hoàn hảo (perfect): mọi nút trong có hai con và mọi lá nằm cùng một cấp

Định lý cây đầy đủ: cây nhị phân đầy đủ có I nút trong thì có đúng I+1 lá. Quan hệ này dùng để ước lượng kích thước cây khi mới biết một nửa thông tin.

Cài đặt cây trong Java

Cấu trúc liên kết

Cài đặt liên kết dùng các nút giữ tham chiếu tới con, và tuỳ chọn tới cha. Linh hoạt, dễ đọc, hợp để hiểu khái niệm.

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

    // Lớp Node lồng nhau - khối xây dựng của cây
    protected static class Node<E> implements Position<E> {
        private E element;          // Dữ liệu chúng ta lưu trữ
        private Node<E> parent;     // Tham chiếu đến cha (null cho gốc)
        private Node<E> left;       // Tham chiếu đến con trái
        private Node<E> right;      // Tham chiếu đến con phải

        public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {
            element = e;
            parent = above;
            left = leftChild;
            right = rightChild;
        }

        public E element() { return element; }
        // ... getters và setters
    }

    private Node<E> root = null;
    private int size = 0;

    // Factory method pattern cho tính linh hoạt
    protected Node<E> createNode(E e, Node<E> parent,
                                 Node<E> left, Node<E> right) {
        return new Node<>(e, parent, left, right);
    }

    // Thêm gốc vào cây rỗng
    public Position<E> addRoot(E e) throws IllegalStateException {
        if (!isEmpty())
            throw new IllegalStateException("Cây không rỗng");
        root = createNode(e, null, null, null);
        size = 1;
        return root;
    }

    // Thêm con - xây dựng gia phả
    public Position<E> addLeft(Position<E> p, E e) {
        Node<E> parent = validate(p);  // Đảm bảo p hợp lệ
        if (parent.left != null)
            throw new IllegalArgumentException("Con trái đã tồn tại");
        Node<E> child = createNode(e, parent, null, null);
        parent.left = child;
        size++;
        return child;
    }
}

createNode() là factory method để lớp con ghi đè. Muốn nút mang thêm thuộc tính, ví dụ màu cho red-black tree hay hệ số cân bằng cho AVL, bạn chỉ ghi đè đúng phương thức này, phần còn lại của cài đặt giữ nguyên.

Cài đặt dựa trên mảng

Với cây nhị phân hoàn chỉnh, biểu diễn mảng bỏ hẳn con trỏ và cho tính cục bộ cache tốt hơn. Đây là lý do heap gần như luôn được cài bằng mảng.

public class ArrayBinaryTree<E> {
    private static final int DEFAULT_CAPACITY = 16;
    private E[] data;
    private int size = 0;

    // Cha và con được xác định bằng phép tính trên chỉ số, không cần con trỏ
    private int parent(int index) {
        if (index == 0) throw new IllegalArgumentException("Gốc không có cha");
        return (index - 1) / 2;
    }
    private int left(int index) { return 2 * index + 1; }
    private int right(int index) { return 2 * index + 2; }

    public void add(E element) {
        if (size >= data.length) resize();
        data[size++] = element;
        // Với heap, chúng ta sẽ bubble up ở đây
    }
}

Cài đặt liên kết rải các nút khắp heap của JVM, mỗi lần đi từ cha xuống con là một lần đọc con trỏ có thể trượt cache. Cài đặt mảng đặt cả một tầng cây nằm liền nhau trong bộ nhớ, nên nút cha và hai con của nó thường rơi vào cùng vài cache line. Đổi lại, xoá một phần tử ở giữa mảng buộc dồn lại các phần tử phía sau.

Đánh đổi giữa các cách cài đặt

Hai cột chèn và xoá của hàng "liên kết" hay bị chép nhầm thành O(1) vô điều kiện. Chúng chỉ là O(1) sau khi bạn đã cầm trong tay Position của nút cần thao tác; đi tìm Position đó tốn O(h).

Bốn cách duyệt cây

Duyệt cây là thăm mỗi nút đúng một lần. Thứ tự thăm quyết định bạn làm được việc gì.

Tiền thứ tự (preorder)

Thứ tự: Gốc → Trái → Phải

public void preorder(Node<E> root) {
    if (root == null) return;

    process(root);           // Thăm thành phố hiện tại trước
    preorder(root.left);     // Khám phá quận bên trái
    preorder(root.right);    // Khám phá quận bên phải
}

Cách nhớ: tiền tố, cha ra TRƯỚC con.

Chỗ dùng thật: sao chép cây thư mục. Phải tạo thư mục cha trước rồi mới đổ nội dung vào, nên thao tác trên cha phải xảy ra trước thao tác trên con. Serialize một cây ra file cũng theo thứ tự này, vì khi đọc lại bạn cần nút cha tồn tại trước khi gắn con vào.

Trung thứ tự (inorder)

Thứ tự: Trái → Gốc → Phải

public void inorder(Node<E> root) {
    if (root == null) return;

    inorder(root.left);      // Thăm quận bên trái trước
    process(root);           // Thăm trung tâm thành phố
    inorder(root.right);     // Thăm quận bên phải cuối cùng
}

Cách nhớ: cha nằm GIỮA hai con.

Trên cây tìm kiếm nhị phân, duyệt trung thứ tự trả ra dãy đã sắp xếp tăng dần. Đó là cách TreeMap của Java lặp qua khoá theo thứ tự, và cũng là lý do một câu ORDER BY trên cột có index B-tree không cần bước sắp xếp riêng.

Hậu thứ tự (postorder)

Thứ tự: Trái → Phải → Gốc

public void postorder(Node<E> root) {
    if (root == null) return;

    postorder(root.left);    // Dọn quận bên trái
    postorder(root.right);   // Dọn quận bên phải
    process(root);           // Cuối cùng dọn trung tâm thành phố
}

Cách nhớ: hậu tố, cha ra SAU con.

Chỗ dùng thật: mọi phép tính mà kết quả ở cha phụ thuộc kết quả ở con. Tính kích thước một thư mục phải cộng xong kích thước các thư mục con. Đánh giá cây biểu thức phải có giá trị hai toán hạng trước khi áp toán tử. Trong C++ hay Rust, giải phóng cây cũng chạy hậu thứ tự: xoá cha trước thì mất luôn đường tới con, và vùng nhớ của con rò ra ngoài. Java có garbage collector nên không gặp vấn đề này, nhưng thứ tự vẫn đúng cho mọi tài nguyên phải đóng tay như file handle hay connection.

Theo cấp (level-order)

Thứ tự: hết cấp này tới cấp khác, mỗi cấp đi từ trái sang phải

public void levelOrder(Node<E> root) {
    if (root == null) return;

    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> current = queue.poll();
        process(current);

        if (current.left != null) queue.offer(current.left);
        if (current.right != null) queue.offer(current.right);
    }
}

Đây là cách duy nhất trong bốn cách không dùng đệ quy, và là BFS áp lên cây. Tính năng "bạn của bạn" trên mạng xã hội chạy đúng thuật toán này: lấy hết người ở khoảng cách 1, rồi mới sang khoảng cách 2.

Thuật toán Morris

Ba cách duyệt đệ quy ở trên tốn O(h) bộ nhớ cho ngăn xếp. Morris duyệt trung thứ tự với O(1) bộ nhớ phụ, bằng cách mượn tạm các con trỏ right đang null của nút lá để làm đường quay về, rồi trả lại nguyên trạng:

public void morrisInorder(Node<E> root) {
    Node<E> current = root;

    while (current != null) {
        if (current.left == null) {
            process(current);
            current = current.right;
        } else {
            // Tìm predecessor trung thứ tự
            Node<E> predecessor = current.left;
            while (predecessor.right != null &&
                   predecessor.right != current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                // Tạo thread
                predecessor.right = current;
                current = current.left;
            } else {
                // Xóa thread và xử lý
                predecessor.right = null;
                process(current);
                current = current.right;
            }
        }
    }
}

Trong lúc chạy, cây bị sửa. Hai luồng cùng duyệt Morris trên một cây sẽ phá nhau, và nếu hàm process() ném exception giữa chừng, cây nằm lại ở trạng thái có thread thừa. Đổi lại, nó chạy được trên thiết bị nhúng mà ngăn xếp không đủ chỗ cho một cây sâu.

Cây chạy ở đâu trong thực tế

Cơ sở dữ liệu

Index của MySQL và PostgreSQL mặc định là B-tree. Mỗi lần bạn SELECT ... WHERE id = ? trên một bảng có index, engine đi xuống một cây B, và số lần đọc đĩa bằng chiều cao cây, thường là 3 hoặc 4 tầng cho bảng hàng trăm triệu dòng.

B-tree ra đời ở phòng nghiên cứu của Boeing khoảng 1970, do Rudolf Bayer và Edward McCreight, công bố trên Acta Informatica năm 1972. Bài toán của họ là quản lý chỉ mục lớn hơn bộ nhớ, nên mỗi nút được thiết kế vừa một khối đĩa và chứa nhiều khoá cùng lúc, đổi chiều cao cây lấy số lần seek.

Chữ "B" trong B-tree chưa bao giờ được hai tác giả xác nhận là viết tắt của gì. Trên trang cá nhân, McCreight kể rằng Bayer hay nói: càng nghĩ lâu về chuyện chữ B có thể mang nghĩa gì, bạn càng hiểu thêm về B-tree. Các phỏng đoán quen thuộc gồm Boeing, balanced, broad, bushy và chính Bayer.

Ngày nay B-tree và các biến thể của nó nằm ở:

• Index của MySQL (InnoDB), PostgreSQL, SQLite
• Hệ thống file: NTFS, btrfs, XFS, APFS, và chỉ mục thư mục HTree của ext4
• MongoDB, qua storage engine WiredTiger

Ngược lại, Google Search không chạy trên B-tree. Tìm kiếm toàn văn dùng inverted index: một bảng ánh xạ từ khoá sang danh sách tài liệu chứa nó, cấu trúc gần với hash map và posting list hơn là cây.

Game và đồ hoạ

• BSP tree (Binary Space Partitioning) là thứ khiến Doom chạy được trên máy 1993: chia không gian thành các nửa mặt phẳng và dựng sẵn thứ tự vẽ, nên engine không phải sắp xếp đa giác theo độ sâu mỗi khung hình
• Scene graph tổ chức vật thể theo thứ bậc, nên khi bạn xoay thân xe, bánh xe đi theo mà không cần tính lại từng bánh
• Quadtree và octree chia không gian để game thế giới mở chỉ nạp và kiểm tra va chạm ở vùng quanh người chơi

Machine learning

• Random Forest và Gradient Boosted Trees (XGBoost, LightGBM) vẫn là lựa chọn đầu tiên cho dữ liệu dạng bảng, và thắng phần lớn các cuộc thi Kaggle về tabular data trong giai đoạn 2015 đến 2020
• Mỗi cây trong rừng là một cây nhị phân nơi nút trong là một câu hỏi về một đặc trưng, và lá là dự đoán
• Cây quyết định được dùng nhiều trong y tế vì đọc ngược lại được: đường đi từ gốc xuống lá chính là chuỗi lý do cho kết luận, thứ mà mạng nơ-ron không đưa ra được

Lịch sử ngắn

Arthur Cayley đặt tên "tree" cho cấu trúc này năm 1857, trong bài "On the theory of the analytical forms called trees". Động lực của ông là phép lấy đạo hàm lặp: đạo hàm một hàm hợp nhiều lần thì các số hạng sinh ra phân nhánh theo đúng dạng cây. Gần 20 năm sau, khoảng 1874 đến 1875, Cayley mới dùng chính công cụ đó để đếm số đồng phân của alkane. Liên hệ giữa cây và hoá học bắt đầu từ đó, chứ không có ở bài 1857.

Những năm 1960 đến 1980 là lúc gần như mọi cây cân bằng còn dùng đến hôm nay được phát minh:

• 1962: Georgy Adelson-Velsky và Evgenii Landis công bố AVL tree trong bài "An algorithm for the organization of information", cây tự cân bằng đầu tiên. Adelson-Velsky bắt đầu dẫn nhóm làm chương trình cờ vua ở Moskva từ năm sau, 1963, và nhóm đó về sau viết Kaissa, chương trình vô địch cờ vua máy tính thế giới đầu tiên năm 1974.
• 1970 đến 1972: B-tree ra đời ở Boeing
• 1978: Leonidas Guibas và Robert Sedgewick công bố red-black tree ở Xerox PARC. Chuyện vì sao là đỏ và đen có hai dị bản, một nói máy in laser màu ở PARC cho ra màu đỏ đẹp nhất, một do chính Guibas kể là vì họ chỉ có bút đỏ và bút đen để vẽ.
• 1985: Daniel Sleator và Robert Tarjan giới thiệu splay tree, cây tự điều chỉnh theo mẫu truy cập

Mỗi cái giải một bài toán riêng: AVL giữ cây cân bằng chặt nhất nên tìm kiếm nhanh nhất, red-black nới ràng buộc để chèn và xoá rẻ hơn, B-tree tối ưu cho đĩa, splay tree đưa nút vừa truy cập lên gần gốc để lần sau nhanh hơn.

Phân tích độ phức tạp

Cây tìm kiếm nhị phân:

• Cây cân bằng: O(log n) cho tìm kiếm, chèn, xoá
• Cây suy biến: O(n), khi cây trở thành danh sách liên kết
• Cây dựng từ dữ liệu ngẫu nhiên: O(log n) trung bình

Bộ nhớ:

• Cài đặt liên kết: O(n) cho các nút
• Ngăn xếp đệ quy khi duyệt: O(h)
• Cài đặt mảng cho cây không hoàn chỉnh: tệ nhất là $O(2^h)$, tức là phải cấp phát chỗ cho cả cây hoàn hảo dù chỉ dùng vài nút

Cây tìm kiếm nhị phân có một tính chất khó chịu: hiệu năng của nó phụ thuộc vào thứ tự bạn chèn dữ liệu vào. Chèn 1, 2, 3 đến n theo đúng thứ tự tăng dần, cái bạn nhận được là danh sách liên kết đội lốt cây, trả đủ chi phí con trỏ mà không hưởng được gì. AVL, red-black và mọi biến thể tự cân bằng đều sinh ra từ chỗ này, để một thứ tự dữ liệu xấu không kéo O(log n) về O(n).

Phần cân bằng đó dài, mình để dành cho một bài khác.

Bình