Trong khoa học máy tính, cây tìm kiếm nhị phân (BST) là một cấu trúc dữ liệucây nhị phâncó gốc với khóa của mỗi nút trung gian có giá trị lớn hơn mọi khóa ở cây con trái và nhỏ hơn mọi khóa ở cây con phải tương ứng. Độ phức tạp thời gian của các phép toán trên cây tìm kiếm nhị phân tỉ lệ thuận với độ cao của cây. Cây tìm kiếm nhị phân cho phép thực thi tìm kiếm nhị phân để truy vấn, chèn và xóa nhanh đối tượng dữ liệu. Vì các nút trong BST được sắp xếp sao cho mỗi phép so sánh bỏ qua khoảng một nửa phần cây còn lại nên hiệu suất truy vấn tỉ lệ thuận theo logarit nhị phân. BST ra đời vào thập niên 1960 để giải quyết bài toán lưu trữ hiệu quả dữ liệu gán nhãn và được cho là do Conway Berners-Lee và David Wheeler phát minh. [ Đọc tiếp ]
