Kỹ sư QLTT Ghi chú ôn thi
← Về danh sách
Điện toán & Nhúng
#트리정렬#이진탐색트리#중위순회#정렬알고리즘#129회
Cập nhật lần cuối · 2026-09-07

Sắp xếp cây (Tree Sort)

1. Tổng quan

A. Định nghĩa

Sắp xếp cây là thuật toán sắp xếp dựa trên so sánh, lần lượt chèn dữ liệu cần sắp xếp vào cây tìm kiếm nhị phân (BST, Binary Search Tree) rồi đọc ra bằng duyệt trung thứ tự (In-order Traversal) để thu được thứ tự tăng dần (hoặc giảm dần). Thuật toán mượn nguyên vẹn bất biến (invariant) 'cây con trái < gốc < cây con phải' của cây tìm kiếm nhị phân để sắp xếp.

Nguyên lý cốt lõi của sắp xếp cây nằm ở tính chất 'duyệt trung thứ tự một cây tìm kiếm nhị phân sẽ tự động cho ra thứ tự đã sắp xếp'. Cây tìm kiếm nhị phân là cấu trúc dữ liệu được tổ chức sao cho, xét tại một nút bất kỳ, cây con trái chỉ chứa giá trị nhỏ hơn nó và cây con phải chỉ chứa giá trị lớn hơn nó. Tính chất này đúng đệ quy tại mọi nút, nên khi thực hiện duyệt trung thứ tự thăm toàn bộ cây theo thứ tự 'trái → gốc → phải', các giá trị sẽ chảy ra theo thứ tự tăng dần từ nhỏ nhất đến lớn nhất. Tức là để đạt mục đích sắp xếp, thay vì thiết kế tường minh logic so sánh·hoán đổi (swap) riêng như sắp xếp nổi bọt·sắp xếp nhanh, chính hành vi chèn dữ liệu vào cây đã là một 'sắp xếp ẩn' đặt mỗi phần tử vào vị trí đúng theo thứ tự độ lớn, còn việc duyệt chỉ là quá trình trải kết quả đó ra và đọc tuyến tính.

Cách tiếp cận này thú vị vì nó cho thấy thuật toán sắp xếp và cấu trúc dữ liệu thực chất là hai mặt của một đồng xu. Quá trình sắp xếp nhanh chia trái phải theo pivot bằng chia để trị đồng cấu (isomorphic) về cấu trúc với quá trình sắp xếp cây tạo cây con trái phải theo gốc. Thực tế, nếu lần theo đúng thứ tự chèn của sắp xếp cây trên dữ liệu ngẫu nhiên, số lần so sánh cho thấy phân phối thống kê giống hệt số lần so sánh của sắp xếp nhanh khi chọn pivot ngẫu nhiên. Vì thế sắp xếp cây còn được gọi là 'sắp xếp nhanh được biểu diễn bằng cấu trúc dữ liệu'.

B. Bối cảnh ra đời và sự cần thiết

Các thuật toán sắp xếp truyền thống (nổi bọt·chèn·chọn·nhanh·trộn, v.v.) thường giả định sắp xếp tĩnh (batch) — 'sắp xếp toàn bộ mảng được cho một lần'. Tuy nhiên trong thực tế có nhiều tình huống động (online) mà dữ liệu liên tục đi vào như một luồng và phải có thể truy vấn·duyệt ở trạng thái đã sắp xếp bất cứ lúc nào. Ví dụ như bảng xếp hạng thời gian thực, duy trì log sự kiện theo thứ tự thời gian, hàng đợi công việc có độ ưu tiên thay đổi. Khi đó, mỗi lần có phần tử mới lại sắp xếp lại toàn bộ mảng trong O(n log n) là lãng phí. Sắp xếp cây xử lý mỗi lần chèn trong O(log n) (khi cân bằng) trong khi bản thân cây luôn duy trì 'trạng thái có thể sắp xếp', nên tự nhiên phù hợp với môi trường động có chèn·xóa lặp lại.

Ngoài ra, sắp xếp cây có giá trị thực tiễn ở chỗ không chỉ cho kết quả sắp xếp mà còn thu được kèm theo nhiều loại truy vấn trên thứ tự đã sắp xếp. Khi duy trì cây, truy vấn giá trị nhỏ nhất·lớn nhất lần lượt là nút trái nhất·phải nhất trong O(log n), tìm sự tồn tại của một giá trị cũng O(log n), và truy vấn phần tử ngay sau (successor)·ngay trước (predecessor) một giá trị cũng có thể thực hiện ngay theo cấu trúc cây. Nếu chỉ cần 'mảng đã sắp xếp' thì sắp xếp nhanh·trộn tốt hơn, nhưng nếu cần 'liên tục duy trì trạng thái đã sắp xếp đồng thời xử lý truy vấn' thì cách tiếp cận dựa trên cây có lợi — đó là lý do học riêng sắp xếp cây.

2. Nguyên lý hoạt động và thủ tục

A. Sơ đồ cấu trúc tổng thể

Sắp xếp cây chia làm hai giai đoạn lớn: 'giai đoạn chèn' và 'giai đoạn duyệt'. Ở giai đoạn chèn, n phần tử mỗi cái tự tìm vị trí của mình trong cây qua so sánh độ lớn, và ở giai đoạn duyệt, cây hoàn chỉnh được duyệt trung thứ tự để xuất kết quả sắp xếp tuyến tính.

flowchart LR
  I["Luồng dữ liệu đầu vào<br/>(chưa sắp xếp)"] --> B["Xây dựng cây tìm kiếm nhị phân<br/>(trái < gốc < phải)"]
  B --> T["Duyệt trung thứ tự<br/>(trái → gốc → phải)"]
  T --> S["Kết quả đã sắp xếp<br/>(tăng dần)"]
  style B fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style S fill:#e6f4ea,stroke:#137333,stroke-width:2px

B. Giai đoạn chèn — tìm đúng vị trí trong cây

Việc chèn bắt đầu từ gốc, tại mỗi nút lặp lại 'nếu giá trị cần chèn nhỏ hơn nút hiện tại thì sang trái, lớn hơn thì sang phải', và khi tới chỗ trống thì gắn nút mới vào đó. Chi phí chèn của mỗi phần tử tỷ lệ với chiều cao của cây tại thời điểm đó. Nếu cây cân bằng tốt, chiều cao khoảng log₂n nên mỗi lần chèn là O(log n), toàn bộ n phần tử là O(n log n). Ngược lại, nếu cây lệch về một phía, chiều cao gần n nên mỗi lần chèn là O(n), toàn bộ xấu đi thành O(n²). Do đó hiệu năng của giai đoạn chèn phụ thuộc hoàn toàn vào việc 'thứ tự đầu vào làm cây cân bằng tới mức nào'.

Lấy ví dụ cụ thể với đầu vào [5, 3, 8, 1, 4, 7, 9]. 5 trở thành gốc, 3 nhỏ hơn 5 nên sang trái, 8 lớn hơn nên sang phải, 1 nhỏ hơn 5·3 nên ở bên trái của 3, 4 nhỏ hơn 5 và lớn hơn 3 nên ở bên phải của 3, 7 lớn hơn 5 và nhỏ hơn 8 nên ở bên trái của 8, 9 lớn hơn 8 nên ở bên phải của 8. Kết quả là một cây tương đối cân bằng có chiều cao 2. Ngược lại, nếu đầu vào đã được sắp xếp [1, 3, 4, 5, 7, 8, 9], mỗi phần tử chỉ gắn vào bên phải nút trước đó, tạo thành 'cây lệch (skewed)' kéo dài về phía phải, không khác gì danh sách liên kết, và chiều cao là n−1.

C. Giai đoạn duyệt trung thứ tự — đọc kết quả sắp xếp

Khi chèn xong, cây được duyệt trung thứ tự. Duyệt trung thứ tự thực hiện đệ quy tại mỗi nút theo thứ tự 'thăm hết cây con trái → xuất chính nó → thăm hết cây con phải'. Duyệt trung thứ tự cây trong ví dụ trên cho ra lần lượt 1, 3, 4, 5, 7, 8, 9, hoàn tất việc sắp xếp. Việc duyệt thăm mỗi nút đúng một lần nên luôn là O(n), không phụ thuộc cây có cân bằng hay không. Do đó nút thắt hiệu năng của sắp xếp cây nằm ở giai đoạn chèn chứ không phải duyệt.

flowchart TB
  R((5))
  R -->|left| A((3))
  R -->|right| B((8))
  A -->|left| C((1))
  A -->|right| D((4))
  B -->|left| E((7))
  B -->|right| F((9))
  style R fill:#fde7e9,stroke:#c5221f,stroke-width:2px

Trong cấu trúc trên, có thể xác nhận thứ tự thăm của duyệt trung thứ tự (1→3→4→5→7→8→9) chính là kết quả sắp xếp tăng dần. Nếu cần thứ tự giảm dần thì thực hiện duyệt trung thứ tự đảo (reverse in-order) theo thứ tự 'phải → gốc → trái'.

D. Ví dụ cài đặt (mã giả)

Sắp xếp cây được biểu diễn gọn gàng bằng hai hàm: hàm chèn và hàm duyệt trung thứ tự. Mã giả dưới đây giả định cây tìm kiếm nhị phân trong đó mỗi nút có giá trị (key) và con trỏ con trái·phải. Việc chèn đệ quy đi xuống tìm vị trí, còn việc sắp xếp tích lũy kết quả duyệt trung thứ tự vào danh sách.

function insert(node, key):
    if node is NULL:
        return new Node(key)          # tạo nút mới tại chỗ trống
    if key < node.key:
        node.left  = insert(node.left, key)   # nhỏ hơn thì sang trái
    else:
        node.right = insert(node.right, key)  # lớn hơn hoặc bằng thì sang phải
    return node

function inorder(node, result):
    if node is NULL: return
    inorder(node.left, result)         # 1) cây con trái
    result.append(node.key)            # 2) xuất chính nó
    inorder(node.right, result)        # 3) cây con phải

function treeSort(array):
    root = NULL
    for key in array:
        root = insert(root, key)       # chèn toàn bộ: trung bình O(n log n)
    result = []
    inorder(root, result)              # duyệt trung thứ tự: O(n)
    return result                      # kết quả đã sắp xếp

Như mã giả cho thấy, độ phức tạp logic của sắp xếp cây rất thấp. Việc sắp xếp hoàn tất chỉ bằng tổ hợp hai thao tác cây chuẩn là 'chèn' và 'duyệt' mà không cần logic hoán đổi·trộn riêng, và sự đơn giản này là lý do sắp xếp cây được dùng rộng rãi làm ví dụ giảng dạy về mối quan hệ giữa cấu trúc dữ liệu và thuật toán. Tuy nhiên cài đặt thuần túy này không bảo đảm cân bằng, nên trong thực tế insert được thay bằng phép chèn cân bằng có bao gồm phép quay của cây AVL·đỏ-đen để ngăn trường hợp xấu nhất.

E. Xử lý giá trị trùng và tính ổn định

Dữ liệu thực tế có thể có nhiều khóa giống nhau. Khi đó phải quy định nhất quán quy tắc xử lý giá trị bằng nhau như 'nhỏ hơn thì sang trái, lớn hơn hoặc bằng thì sang phải', nếu không vị trí chèn của khóa trùng sẽ mơ hồ. Ngoài ra, sắp xếp cây về cơ bản không phải sắp xếp ổn định (stable sort). Tức là không có bảo đảm rằng thứ tự đầu vào ban đầu của các phần tử có khóa bằng nhau được giữ nguyên sau khi sắp xếp. Nếu cần tính ổn định, phải mở rộng để mỗi nút lưu thêm 'thời điểm chèn (số thứ tự)' làm khóa phụ, và khi khóa bằng nhau thì so sánh lần hai theo số thứ tự. Những xử lý chi tiết này không thể hiện được chỉ qua bảng, và là hạng mục thiết kế nhất định phải quyết định khi cài đặt thực tế.

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

Độ phức tạp thời gian·không gian của sắp xếp cây thay đổi lớn tùy trạng thái cân bằng của cây, và hiểu chính xác điều này là cốt lõi của thuật toán.

Phân loại Độ phức tạp thời gian Điều kiện xảy ra Ghi chú
Trung bình (đầu vào ngẫu nhiên) O(n log n) Dữ liệu trộn ngẫu nhiên, gần cân bằng Chèn n×O(log n) + duyệt O(n)
Tốt nhất O(n log n) Thứ tự chèn gần cân bằng hoàn toàn Ngang với trường hợp tốt nhất của sắp xếp nhanh
Xấu nhất (cây lệch) O(n²) Đầu vào đã sắp xếp·sắp xếp ngược Cây lệch → chèn suy biến thành O(n)
Không gian O(n) Luôn luôn Lưu n nút (không phải sắp xếp tại chỗ)

Biến số quyết định hiệu năng của sắp xếp cây là 'đầu vào làm cây cân bằng tới mức nào'. Dữ liệu trộn ngẫu nhiên khiến các phần tử phân tán đều trái phải, chiều cao cây về mặt thống kê ở mức khoảng 1.39·log₂n, cho trung bình O(n log n). Nhưng nếu đưa vào dữ liệu đã sắp xếp tăng dần hoặc giảm dần, mọi phần tử chỉ gắn về một phía tạo thành cây lệch chiều cao n−1, việc chèn phần tử thứ i cần i−1 lần so sánh, tổng số lần so sánh là 1+2+…+(n−1) ≈ n²/2, tức xấu đi thành O(n²). Ví dụ nếu 10,000 phần tử đã được sắp xếp, số lần so sánh khi chèn — vốn chỉ khoảng 130 nghìn lần (≈ n·log₂n) nếu ngẫu nhiên — sẽ bùng nổ lên khoảng 50 triệu lần (≈ n²/2). Đây là lý do sắp xếp cây ở dạng thuần túy ít được dùng trong thực tế và luôn được bàn cùng với cây cân bằng.

Về không gian, sắp xếp cây là sắp xếp không tại chỗ (out-of-place), đòi hỏi không gian lưu trữ cây riêng O(n) tỷ lệ với kích thước đầu vào. Đây là nhược điểm so với sắp xếp vun đống cần O(1) không gian bổ sung hoặc sắp xếp nhanh cần O(log n) (ngăn xếp đệ quy), và có thể là gánh nặng trong môi trường nhúng có bộ nhớ eo hẹp.

4. So sánh với các thuật toán sắp xếp·cấu trúc dữ liệu khác

Để hiểu đúng sắp xếp cây, cần nắm cả 'lý do tạo ra khác biệt' với các thuật toán tương tự. Bảng dưới đây là điểm xuất phát của việc so sánh, còn bối cảnh của mỗi khác biệt được bổ sung bằng văn xuôi.

Thuật toán Thời gian trung bình Thời gian xấu nhất Không gian Tính ổn định Đặc điểm
Sắp xếp cây O(n log n) O(n²) O(n) Không ổn định (có thể khi mở rộng) Có lợi cho chèn·truy vấn động
Sắp xếp nhanh O(n log n) O(n²) O(log n) Không ổn định Sắp xếp tại chỗ hiệu quả cache cao
Sắp xếp trộn O(n log n) O(n log n) O(n) Ổn định Hiệu năng ổn định cả khi xấu nhất
Sắp xếp vun đống O(n log n) O(n log n) O(1) Không ổn định Cấu trúc cây (heap) nhưng tại chỗ

Sắp xếp cây và sắp xếp vun đống đều dùng cấu trúc cây nhưng khác nhau về mục đích và cài đặt. Sắp xếp vun đống biểu diễn ngầm heap dạng 'cây nhị phân hoàn chỉnh' trên mảng để sắp xếp tại chỗ với O(1) không gian bổ sung, và bảo đảm O(n log n) cả khi xấu nhất. Ngược lại, sắp xếp cây tạo cây tìm kiếm nhị phân dựa trên con trỏ tường minh ở vùng nhớ riêng, dùng O(n) không gian, và có thể suy biến thành O(n²) khi mất cân bằng. Đổi lại, sắp xếp cây giữ cây sau khi sắp xếp nên có thể tiếp tục truy vấn successor/predecessor hoặc tìm kiếm theo khoảng, trong khi heap chỉ lấy nhanh được một giá trị lớn nhất (hoặc nhỏ nhất) nên không phù hợp cho truy vấn phần tử bất kỳ. Tức là hàm ý thực tiễn là: nếu 'sắp xếp một lần rồi thôi' thì heap·nhanh tốt hơn, còn nếu 'duy trì trạng thái sắp xếp và tiếp tục truy vấn' thì dựa trên cây tốt hơn.

Lý do sắp xếp cây và sắp xếp nhanh có cùng độ phức tạp trung bình·xấu nhất nhưng mức ưa chuộng trong thực tế khác nhau nằm ở tính cục bộ cache (cache locality) và mẫu truy cập bộ nhớ. Sắp xếp nhanh xử lý mảng in-place trên vùng nhớ liên tục nên tỷ lệ trúng cache CPU cao, trong khi sắp xếp cây phải đi theo các nút rải rác bằng con trỏ nên cache miss thường xuyên, khiến dù cùng O(n log n) tốc độ đo thực tế thường chậm hơn. Việc dù độ phức tạp lý thuyết như nhau nhưng hiệu năng thực tế khác nhau do hằng số và đặc tính truy cập bộ nhớ là điều nhất định phải cân nhắc khi chọn thuật toán.

5. Nâng cao — Tránh trường hợp xấu nhất bằng cây tìm kiếm nhị phân cân bằng và ứng dụng

Cách giải quyết tận gốc trường hợp xấu nhất O(n²) của sắp xếp cây là dùng cây tìm kiếm nhị phân tự cân bằng (self-balancing BST). Tiêu biểu có cây AVL và cây đỏ-đen (Red-Black). Cây AVL duy trì nghiêm ngặt chênh lệch chiều cao giữa cây con trái và phải tại mọi nút không quá 1, bằng cách cân bằng lại qua phép quay (rotation) mỗi khi chèn·xóa. Kết quả là dù thứ tự đầu vào thế nào, chiều cao cây luôn được bảo đảm O(log n), nên kể cả đưa vào dữ liệu đã sắp xếp thì chèn vẫn giữ O(log n) và toàn bộ là O(n log n). Cây đỏ-đen đặt điều kiện cân bằng có phần lỏng hơn (dựa trên quy tắc màu) để giảm số lần quay, đổi lại quản lý cận trên chiều cao là 2·log₂(n+1); trong tình huống chèn·xóa thường xuyên, chi phí cân bằng lại thấp hơn AVL nên được dùng rộng rãi hơn trong thực tế.

Thực tế, container có thứ tự trong nhiều thư viện chuẩn sử dụng nguyên lý này. Ví dụ std::map·std::set của C++ STL, TreeMap·TreeSet của Java được cài đặt bên trong bằng cây đỏ-đen, chỉ cần chèn phần tử là luôn duy trì trạng thái đã sắp xếp trong O(log n). Duyệt các container này tự động cho ra thứ tự đã sắp xếp — đó chính là dạng thực chiến của 'sắp xếp cây được ổn định hóa bằng cây cân bằng'. Tức là sắp xếp cây không dừng ở thuật toán học tập mà còn sống như nền tảng lý thuyết của các cấu trúc dữ liệu có thứ tự mà ta dùng hằng ngày.

Một ứng dụng nâng cao khác là chỉ mục của cơ sở dữ liệu và hệ thống tệp. B-tree·B+tree là cây tìm kiếm cân bằng đa nhánh (multi-way) chứ không phải nhị phân, được tối ưu cho truy cập theo đơn vị khối đĩa. Chúng cũng là sự mở rộng sang môi trường đĩa của ý tưởng cốt lõi của sắp xếp cây: 'chèn thì duy trì thứ tự, duyệt thì ra kết quả sắp xếp, tăng tốc tìm kiếm theo khoảng'. Trong cơ sở dữ liệu quan hệ, khi dùng ORDER BY trên cột có chỉ mục thì thu được kết quả sắp xếp chỉ bằng duyệt chỉ mục mà không cần sắp xếp riêng, cũng theo cùng nguyên lý. Như vậy, ý tưởng của sắp xếp cây đã được mở rộng rộng rãi từ lý thuyết thuật toán tới toàn bộ việc lập chỉ mục của phần mềm hệ thống.

6. Các lưu ý và hàm ý

Từ góc nhìn Kỹ sư chuyên nghiệp Quản lý Thông tin, sắp xếp cây nên được tiếp cận như một ví dụ minh họa nguyên lý 'lựa chọn cấu trúc dữ liệu quyết định hiệu năng thuật toán', vượt lên hiệu năng của một thuật toán đơn lẻ.

  1. Loại bỏ trường hợp xấu nhất ngay ở giai đoạn thiết kế bằng cây cân bằng. Sắp xếp cây thuần túy dễ tổn thương O(n²) trước đầu vào đã sắp xếp·sắp xếp ngược, nên khi áp dụng thực tế phải lấy cây tự cân bằng như AVL·đỏ-đen làm tiền đề cơ bản để bảo đảm O(n log n). Nếu không thể dự đoán đầu vào đã được sắp xếp trước hay chưa thì chọn cây cân bằng là bắt buộc chứ không phải tùy chọn.
  2. Chọn chiến lược sắp xếp phù hợp với đặc tính workload. Nếu 'chỉ cần kết quả sắp xếp một lần' thì sắp xếp nhanh hiệu quả cache cao hoặc sắp xếp trộn ổn định ở trường hợp xấu nhất có lợi; nếu 'liên tục duy trì trạng thái sắp xếp và lặp lại chèn·xóa·truy vấn' thì cách tiếp cận dựa trên cây tìm kiếm nhị phân cân bằng có lợi. Đánh đổi phải được cân nhắc không chỉ về độ phức tạp thời gian mà cả không gian·tính ổn định·phạm vi hỗ trợ truy vấn.
  3. Xét đồng thời ràng buộc bộ nhớ·cache. Sắp xếp cây kéo theo chi phí O(n) không gian bổ sung và cache miss do đi theo con trỏ. Trong môi trường bộ nhớ và cache hạn chế như nhúng·di động, sắp xếp tại chỗ (vun đống·nhanh) hoặc cấu trúc dữ liệu dựa trên mảng có thể phù hợp hơn, nên phải quyết định phản ánh cả ràng buộc vật lý của môi trường thực thi chứ không chỉ độ phức tạp lý thuyết.
  4. Định nghĩa trước yêu cầu về tính ổn định. Với nghiệp vụ cần giữ nguyên thứ tự ban đầu của các khóa bằng nhau sau khi sắp xếp (tính ổn định) (ví dụ sắp xếp nhiều cấp, xử lý đồng hạng), sắp xếp cây cần mở rộng thêm khóa phụ là số thứ tự. Nếu không làm rõ quy tắc tính ổn định·xử lý khóa trùng ở giai đoạn phân tích yêu cầu, có thể dẫn tới lỗi sắp xếp tinh vi sau khi cài đặt.
  5. Hiểu mối liên hệ với phần mềm hệ thống. Ý tưởng của sắp xếp cây mở rộng tới các container có thứ tự của STL/JCF, chỉ mục B+tree của cơ sở dữ liệu, lập chỉ mục hệ thống tệp. Không nên kết thúc ở một bài toán thuật toán đơn giản mà cần tư duy liên kết với thiết kế chỉ mục·tối ưu truy vấn theo góc nhìn 'cấu trúc dữ liệu duy trì thứ tự' — đó là cách tiếp cận ở tầm Kỹ sư chuyên nghiệp.

Tóm tắt một câu: Sắp xếp cây là thuật toán chèn vào cây tìm kiếm nhị phân rồi sắp xếp bằng duyệt trung thứ tự, trung bình O(n log n) nhưng với đầu vào đã sắp xếp thì xấu đi tới O(n²) do cây lệch, nên loại bỏ trường hợp xấu nhất bằng cây tự cân bằng như AVL·đỏ-đen, và ý tưởng của nó sống trong các môi trường dữ liệu động cần duy trì trạng thái sắp xếp đồng thời xử lý truy vấn (STL map, chỉ mục B+tree của DB).