Làm thế nào để tìm kiếm giá trị lớn nhất hoặc nhỏ nhất trong một Cây tìm kiếm nhị phân (Binary Search Tree - BST) và tại sao việc này lại có hiệu suất cao?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Cây tìm kiếm nhị phân (Binary Search Tree - BST) tuân thủ quy tắc nghiêm ngặt: với bất kỳ nút nào, toàn bộ các nút bên cây con bên trái đều có giá trị nhỏ hơn nút đó, và toàn bộ các nút bên cây con bên phải đều có giá trị lớn hơn.
Cơ chế tìm kiếm Min / Max
Nhờ tính chất sắp xếp này của BST, việc tìm giá trị nhỏ nhất hoặc lớn nhất không cần phải duyệt toàn bộ các nút trên cây:

Tìm giá trị nhỏ nhất (Min): Bắt đầu từ gốc và liên tục rẽ sang nhánh con bên trái cho đến khi không còn nút con trái nào nữa. Nút cuối cùng đó chính là giá trị nhỏ nhất.
Tìm giá trị lớn nhất (Max): Bắt đầu từ gốc và liên tục rẽ sang nhánh con bên phải cho đến khi không còn nút con phải nào nữa. Nút cuối cùng đó chính là giá trị lớn nhất.

Ví dụ mã nguồn minh họa bằng JavaScript
// Tìm giá trị nhỏ nhất trong BST
function findMin(root) {
    if (!root) return null;
    let current = root;
    while (current.left !== null) {
        current = current.left;
    }
    return current.val;
}

// Tìm giá trị lớn nhất trong BST
function findMax(root) {
    if (!root) return null;
    let current = root;
    while (current.right !== null) {
        current = current.right;
    }
    return current.val;
}
Độ phức tạp

Độ phức tạp thời gian (Time Complexity): 
Trường hợp tốt / Trung bình: O(log N) với cây cân bằng.
Trường hợp xấu nhất: O(N) khi cây bị suy biến thành dạng danh sách liên kết (Linked List).

Độ phức tạp không gian (Space Complexity): O(1) nếu sử dụng vòng lặp (while), hoặc O(H) (với H là chiều cao của cây) nếu viết bằng đệ quy do tốn bộ nhớ Call Stack.

Kinh nghiệm thực chiến cho Junior

Không bao giờ dùng thuật toán duyệt toàn bộ cây (như DFS/BFS) để tìm min/max trong một BST vì sẽ làm lãng phí tài nguyên tính toán với độ phức tạp O(N).
Luôn kiểm tra xem cây có bị suy biến hay không trong môi trường thực tế để áp dụng các giải pháp cân bằng cây tự động.

Làm thế nào để tìm kiếm giá trị lớn nhất hoặc nhỏ nhất trong một Cây tìm kiếm nhị phân (Binary Search Tree - BST) và tại sao việc này lại có hiệu suất cao?

Bản chất cơ chế hoạt động

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề