Search tree là gì?

Trong khoa học máy tính, cây tìm kiếm (search tree) là một cấu trúc dữ liệu (data structure ) dạng cây (tree) được sử dụng để định vị các khóa (key) cụ thể từ bên trong một tập hợp (set). Để một cây hoạt động như một cây tìm kiếm (search tree), khóa cho mỗi nút (node) phải lớn hơn bất kỳ khóa nào trong cây con (subtree) ở bên trái và nhỏ hơn bất kỳ khóa nào trong cây con ở bên phải.

Ưu điểm của cây tìm kiếm (search tree) là thời gian tìm kiếm (search time) hiệu quả của chúng do cây được cân bằng hợp lý, nghĩa là các nút lá (leave) ở hai đầu có độ sâu (depth) tương đương. Các cấu trúc dữ liệu (data structure) cây tìm kiếm (search tree) khác nhau tồn tại, một số cấu trúc trong số đó cũng cho phép chèn và xóa các phần tử (element) một cách hiệu quả, mà các thao tác (operation) sau đó phải duy trì sự cân bằng (balance) của cây.

Cây tìm kiếm (search tree) thường được sử dụng để triển khai (implement) một mảng kết hợp (associative array). Thuật toán cây tìm kiếm (search tree) sử dụng khóa từ cặp key–value để tìm một vị trí và sau đó ứng dụng lưu trữ toàn bộ cặp key–value tại vị trí cụ thể đó.

Một số loại cây tìm kiếm (search tree) như cây tìm kiếm nhị phân (binary search tree), b-tree, cây tìm kiếm bậc ba (ternary search tree).