Cây bst là gì
Cây nhị phân tìm kiếm (Binary Search Tree)Cấu trúc dữ liệu cây (tree) bao gồm 1 nút gốc (root) và các nút con (children), các nút con lại bao gồm nút con khác của nó, tạo thành cấu trúc dữ liệu dạng phân cấp (hierachy) bắt đầu từ gốc và phình ra ở dưới (bottom). Show
Cây nhị phân là cấu trúc dữ liệu dạng cây trong đó mỗi nút có tối đa 2 nút con, đây là cấu trúc dữ liệu phổ biến và rất hữu dụng trong khoa học máy tính. Ví dụ cây nhị phân có 8 nút được biểu diễn như hình sau:
Với mỗi nút ta có thể có nút con trái và/hoặc nút con phải, trong trường hợp chỉ có 1 nút con ta có thể coi nó là nút con trái.
Các trạng thái cây nhị phânĐể tiện lợi chúng ta gọi tên các trạng thái của cây nhị phân như sau Cây nhị phân đầy đủ (Full Binary Tree)Mỗi nút có chính xác 0 hoặc 2 nút con.
Tính chất:
Cây nhị phân hoàn thiện (Complete Binary Tree)
Tính chất:
Cây nhị phân hoàn hảo (Perfect Binary Tree)Là cây nhị phân trong đó tất cả nút trong đều có 2 nút con và tất cả nút lá đều ở cùng độ sâu.
Tính chất
Cây cân bằng (Balanced Binary Tree)Cây cân bằng là cây nhị phân trong đó với chính nó và mọi cây con (subtree) độ cao của cây con trái và độ cao của cây con phải sai khác nhau nhiều nhất là 1. Ví dụ cây cân bằng
Cây không cân bằng
Cách biểu diễn (Representation)
Sử dụng mảng (array)
Khi dùng mảng chúng ta cần phân phối vùng nhớ cho Nếu i là chỉ số của phần tử cha thì phần tử con trái nằm ở vị trí 2i + 1, phần tử con phải nằm ở vị trí 2i + 2. Sử dụng danh sách liên kết (linked list)Với danh sách liên kết ta sử dụng cấu trúc dữ liệu như sau (
Cây nhị phân tìm kiếm (Binary Search Tree - BST)Cây nhị phân tìm kiếm là cây nhị phân mà trong đó với chính nó và mọi cây con của nó
Ví dụ cây nhị phân tìm kiếm
Độ cao trung bình của 1 cây nhị phân được sinh ra ngẫu nhiên là O(log n), do đó thời gian thao tác trung bình trên cây nhị phân là O(log n). Tuy nhiên có những trường hợp độ cao cây nhị phân có thể lớn hơn nhiều, trong trường hợp xấu nhất độ cao cây có thể là O(n) do đó thời gian thao tác cũng là O(n). Chúng ta xem xét các ví dụ sau:
Thao tác (operations)
Tìm kiếm (search)Để tìm kiếm 1 phần tử trong cây nhị phân tìm kiếm ta bắt đầu từ gốc của cây:
Minh họa quá trình tìm kiếm số 25 trong cây nhị phân tìm kiếm như sau:
Với cây nhị phân tìm kiếm cân bằng như trên với mỗi phép so sánh ta loại trừ được 1 nửa số phần tử của tập cần tìm. Min và Max
Tìm phần tử sau (Successor) và trước (Predecessor)Nút trước và nút sau trong cây nhị phân tìm kiếm được xác định bởi thứ tự các nút được sắp xếp tăng dần (theo trình tự duyệt giữa). Ví dụ ta có nút x trong cây nhị phân tìm kiếm, các bước để tìm nút sau và nút trước như sau
Thêm (insert)Ví dụ 1. Thêm số 24 vào cây nhị phân tìm kiếm
Ví dụ 2. Thêm lần lượt các phần tử sau vào cây nhị phân rỗng ban đầu:
Xóa (delete)Để xóa 1 nút trên cây nhị phân tìm kiếm ta cần đảm bảo các nút còn lại vẫn thỏa mãn tính chất của cây nhị phân tìm kiếm: tất cả các nút thuộc cây con trái <= nút gốc <= tất cả các nút thuộc cây con phải. Ví dụ x là nút cần xóa, ta xét 3 trường hợp như sau:
Ví dụ trường hợp 3, xóa nút gốc 36 trong cây nhị phân tìm kiếm sau
Mã nguồnTypescript
Minh hoạ trực quanCác bạn nhập input cho các thao tác Insert, Delete để xem cách thuật toán hoạt động theo từng bước. |