Login

Cây (tree) và cây nhị phân tìm kiếm: cấu trúc phân cấp trong lập trình

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Thư mục trên máy tính, cấu trúc HTML của một trang web, sơ đồ tổ chức công ty: tất cả đều có dạng cây. Cây là cấu trúc dữ liệu dùng để biểu diễn mọi thứ có quan hệ cha-con, và là chủ đề xuất hiện thường xuyên trong phỏng vấn.

Các khái niệm cơ bản

  • Nút (node): một phần tử của cây.
  • Gốc (root): nút trên cùng, không có cha.
  • Cha, con: nút nối trực tiếp ở trên và dưới.
  • Lá (leaf): nút không có con.
  • Chiều cao: số tầng từ gốc đến lá xa nhất.

Điểm khác biệt với đồ thị tổng quát: cây không có chu trình, và mỗi nút (trừ gốc) có đúng một cha.

Cây nhị phân

Trong cây nhị phân (binary tree), mỗi nút có tối đa hai con: con trái và con phải. Cài đặt đơn giản:

class Node:
    def __init__(self, gia_tri):
        self.gia_tri = gia_tri
        self.trai = None
        self.phai = None

goc = Node(10)
goc.trai = Node(5)
goc.phai = Node(15)

Duyệt cây

Có ba cách duyệt theo chiều sâu phổ biến, khác nhau ở thời điểm thăm nút gốc:

def trung_thu_tu(nut):      # trái - gốc - phải
    if nut:
        trung_thu_tu(nut.trai)
        print(nut.gia_tri)
        trung_thu_tu(nut.phai)

def tien_thu_tu(nut):       # gốc - trái - phải
    if nut:
        print(nut.gia_tri)
        tien_thu_tu(nut.trai)
        tien_thu_tu(nut.phai)

Hậu thứ tự (trái - phải - gốc) thì thăm gốc cuối cùng. Ngoài ra còn duyệt theo tầng (chiều rộng) dùng hàng đợi. Duyệt cây gần như luôn viết bằng đệ quy vì cấu trúc cây tự lặp lại: mỗi cây con cũng là một cây.

Cây nhị phân tìm kiếm (BST)

Cây nhị phân tìm kiếm có quy tắc: với mọi nút, các giá trị ở cây con trái nhỏ hơn nút, các giá trị ở cây con phải lớn hơn nút. Nhờ vậy việc tìm kiếm giống như tìm nhị phân: mỗi bước loại bỏ một nửa.

def them(nut, gia_tri):
    if nut is None:
        return Node(gia_tri)
    if gia_tri < nut.gia_tri:
        nut.trai = them(nut.trai, gia_tri)
    elif gia_tri > nut.gia_tri:
        nut.phai = them(nut.phai, gia_tri)
    return nut

def tim(nut, gia_tri):
    if nut is None:
        return False
    if gia_tri == nut.gia_tri:
        return True
    if gia_tri < nut.gia_tri:
        return tim(nut.trai, gia_tri)
    return tim(nut.phai, gia_tri)

goc = None
for x in [8, 3, 10, 1, 6, 14]:
    goc = them(goc, x)
print(tim(goc, 6))    # True
print(tim(goc, 7))    # False

Một tính chất thú vị: duyệt BST theo trung thứ tự cho ra dãy đã sắp xếp tăng dần.

Độ hiệu quả và cây cân bằng

Nếu cây "cân đối", chiều cao xấp xỉ log2 của số nút, nên tìm, thêm, xóa đều nhanh. Nhưng nếu bạn thêm lần lượt các số đã sắp xếp 1, 2, 3, 4..., cây biến thành một đường thẳng giống danh sách liên kết và mất hết lợi thế. Để tránh điều này có các loại cây tự cân bằng như AVL hay cây đỏ-đen, tự điều chỉnh sau mỗi lần thêm xóa.

Cây ở khắp nơi

  • Hệ thống file: thư mục chứa thư mục con.
  • DOM của trang web: thẻ HTML lồng nhau.
  • Cơ sở dữ liệu: nhiều hệ quản trị dùng biến thể cây (như B-tree) cho chỉ mục.
  • Cây quyết định trong học máy và trò chơi.

Bài tập với cây nhị phân

Với cấu trúc Node ở trên, hãy thử ba bài sau, tất cả đều giải bằng đệ quy ngắn:

def chieu_cao(nut):
    if nut is None:
        return 0
    return 1 + max(chieu_cao(nut.trai), chieu_cao(nut.phai))

def dem_nut(nut):
    if nut is None:
        return 0
    return 1 + dem_nut(nut.trai) + dem_nut(nut.phai)

def tim_nho_nhat(nut):
    while nut.trai:
        nut = nut.trai
    return nut.gia_tri

Hàm đầu tính chiều cao: cây rỗng cao 0, còn lại là 1 cộng chiều cao của nhánh cao hơn. Hàm thứ hai đếm số nút. Hàm thứ ba tận dụng tính chất của BST: giá trị nhỏ nhất luôn ở nút trái nhất. Sau đó, hãy thử bài khó hơn: kiểm tra một cây nhị phân có phải là BST hợp lệ không (gợi ý: truyền khoảng giá trị cho phép xuống các cây con).

Lỗi thường gặp với cây

  1. Quên trường hợp cây rỗng (nut is None) và gây lỗi truy cập thuộc tính.
  2. Quên gán lại kết quả khi thêm vào BST đệ quy, ví dụ viết them(nut.trai, x) thay vì nut.trai = them(nut.trai, x).
  3. Nhầm giữa chiều cao và độ sâu: độ sâu đo từ gốc xuống nút, chiều cao đo từ nút xuống lá xa nhất.
  4. Giả định BST luôn nhanh mà quên rằng nó có thể bị lệch.

Kết luận

Cây giúp biểu diễn dữ liệu phân cấp và tìm kiếm hiệu quả khi được giữ cân bằng. Hãy bắt đầu bằng việc vẽ cây ra giấy, rồi tự viết hàm thêm, tìm và duyệt. Khi đã quen đệ quy trên cây, nhiều bài toán khó sẽ trở nên dễ thở hơn.

Nếu cần một lộ trình rõ ràng thay vì tự mò mẫm, codebem.com có nhiều khóa học phù hợp cho người mới.

author_photo
Nguyễn Đình Cường

0 comment