Khi triển khai kiểu dữ liệu trừu tượng Dictionary (từ điển), nút liên kết với giá trị. Dictionary cơ bản là tập khóa từ một thứ tự toàn phần (total ordering). Có thể có thông tin bổ sung gắn với khóa, nhưng không ảnh hưởng khái niệm.
Nếu dùng cây, mỗi nút giữ khóa duy nhất. Với mỗi nút u, mọi khóa trong u.left < u.key, mọi khóa trong u.right > u.key. Cây tổ chức theo bất biến này gọi là Binary Search Tree (BST).
Lợi thế lớn: danh sách khóa sắp xếp thu được trong thời gian tuyến tính bằng duyệt in-order. Định nghĩa đệ quy: cây rỗng không làm gì, ngược lại đệ quy cây trái, xử lý gốc, đệ quy cây phải.
Có nhiều thao tác trên BST. Tìm kiếm dựa trên chiều cao cây. Tìm kiếm là thao tác quan trọng nhất.