Tổng quan
Tìm kiếm trên Cây Tìm Kiếm Nhị Phân định vị một khóa bằng cách tận dụng thứ tự của BST: tại mỗi nút, nó so sánh giá trị cần tìm với khóa của nút và đi sang trái nếu nhỏ hơn hoặc sang phải nếu lớn hơn, loại bỏ một nửa cây còn lại ở mỗi bước.
Đây là phiên bản trên cây của tìm kiếm nhị phân trên mảng đã sắp, đi theo một đường duy nhất từ gốc tới lá nên số phép so sánh bị chặn bởi chiều cao cây.
Tìm kiếm trên BST hoạt động thế nào?
- Bắt đầu tại nút gốc.
- So sánh khóa cần tìm với khóa của nút hiện tại; nếu bằng nhau, tìm kiếm thành công.
- Nếu khóa cần tìm nhỏ hơn, đi sang nút con trái; nếu lớn hơn, đi sang nút con phải.
- Dừng khi tìm thấy khóa hoặc gặp liên kết null, nghĩa là khóa không tồn tại.
Khi nào nên dùng?
- Kiểm tra thành viên và tra cứu nhanh trong các cấu trúc dữ liệu có thứ tự trong bộ nhớ như tập hợp và ánh xạ.
- Truy vấn theo khoảng và tìm khóa gần nhất, vì thứ tự dẫn đường cho quá trình đi.
- Cùng logic so sánh này là nền tảng cho thao tác chèn và xóa trên BST.
Phân tích độ phức tạp
Mỗi phép so sánh đi xuống một mức, nên tìm kiếm tốn O(h) với h là chiều cao cây. Một BST cân bằng giữ h ở mức O(log n) cho tìm kiếm logarit, nhưng cây suy biến dạng chuỗi (ví dụ dựng từ chèn dữ liệu đã sắp) có h bằng n, làm tìm kiếm xuống O(n). Bộ nhớ là O(1) khi lặp hoặc O(h) khi đệ quy.
Câu hỏi thường gặp
Vì sao tìm kiếm BST có thể xuống O(n)?
Nếu các khóa được chèn theo thứ tự đã sắp, cây trở thành một chuỗi thẳng có chiều cao n, nên tìm kiếm có thể phải đi qua mọi nút. Các cây tự cân bằng như AVL hay Đỏ-Đen giữ chiều cao ở O(log n) để ngăn điều này.
Tìm kiếm BST liên hệ thế nào với tìm kiếm nhị phân trên mảng?
Cả hai đều chia đôi không gian tìm kiếm sau mỗi phép so sánh. Tìm kiếm nhị phân làm điều đó trên mảng đã sắp tĩnh, còn BST cân bằng làm trên một cấu trúc động hỗ trợ cả chèn và xóa hiệu quả.