Trong bài toán tìm kiếm giá trị lớn nhất hoặc nhỏ nhất trong một cây nhị phân tìm kiếm (BST), tại sao chúng ta chỉ cần đi theo một hướng duy nhất thay vì duyệt toàn bộ cây?

Question

Accepted Answer

Bản chất của BST
Cây tìm kiếm nhị phân (BST) duy trì tính chất: mọi nút ở nhánh trái đều nhỏ hơn nút gốc, và mọi nút ở nhánh phải đều lớn hơn nút gốc. Tính chất này được bảo toàn đệ quy trên toàn bộ các cây con.
Chiến lược tìm kiếm

Tìm giá trị nhỏ nhất: Luôn đi theo các con trỏ bên trái (left child) cho đến khi gặp nút không còn con trái.
Tìm giá trị lớn nhất: Luôn đi theo các con trỏ bên phải (right child) cho đến khi gặp nút không còn con phải.

Hiệu năng

Độ phức tạp thời gian: O(h) với h là chiều cao của cây. Trong trường hợp cây cân bằng, độ phức tạp là O(log n).
Việc không duyệt toàn bộ cây giúp giảm đáng kể số lần truy cập vào bộ nhớ, đặc biệt quan trọng khi dữ liệu được lưu trữ trên đĩa hoặc trong các cấu trúc dữ liệu phân tán.

Trong bài toán tìm kiếm giá trị lớn nhất hoặc nhỏ nhất trong một cây nhị phân tìm kiếm (BST), tại sao chúng ta chỉ cần đi theo một hướng duy nhất thay vì duyệt toàn bộ cây?

Bản chất của BST

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ủ đề