Cây tìm kiếm nhị phân¶

Như được hiển thị trong hình bên dưới, một cây tìm kiếm nhị phân (binary search tree) thỏa mãn các điều kiện dưới đây.

Đối với nút gốc (root node), giá trị của tất cả các nút trong cây con bên trái (left subtree) \(<\) giá trị của nút gốc \(<\) giá trị của tất cả các nút trong cây con bên phải (right subtree).
Các cây con bên trái và bên phải của bất kỳ nút nào cũng đều là cây tìm kiếm nhị phân, tức là chúng cũng thỏa mãn điều kiện 1..

Các thao tác trên cây tìm kiếm nhị phân¶

Chúng ta đóng gói cây tìm kiếm nhị phân thành lớp BinarySearchTree và khai báo một biến thành viên root trỏ đến nút gốc của cây.

Tìm kiếm nút¶

Cho trước giá trị nút mục tiêu num, chúng ta có thể tìm kiếm dựa trên các tính chất của cây tìm kiếm nhị phân. Như được hiển thị trong hình bên dưới, chúng ta khai báo một nút cur và bắt đầu từ nút gốc root của cây tìm kiếm nhị phân, lặp lại việc so sánh cur.val với num.

Nếu cur.val < num, điều đó có nghĩa là nút mục tiêu nằm trong cây con bên phải của cur, do đó thực hiện cur = cur.right.
Nếu cur.val > num, điều đó có nghĩa là nút mục tiêu nằm trong cây con bên trái của cur, do đó thực hiện cur = cur.left.
Nếu cur.val = num, điều đó có nghĩa là đã tìm thấy nút mục tiêu, thoát khỏi vòng lặp và trả về nút đó.

<1><2><3><4>

Thao tác tìm kiếm trên cây tìm kiếm nhị phân tuân theo nguyên lý tương tự như tìm kiếm nhị phân (binary search): mỗi vòng lặp sẽ loại bỏ một nửa số trường hợp còn lại. Số lần lặp tối đa bằng chiều cao của cây. Khi cây cân bằng, việc tìm kiếm mất thời gian \(O(\log n)\). Mã ví dụ như sau:

[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{search}

Chèn nút¶

Cho trước phần tử num cần chèn, để duy trì tính chất "cây con bên trái < nút gốc < cây con bên phải" của cây tìm kiếm nhị phân, quy trình chèn sẽ diễn ra như trong hình bên dưới.

Tìm kiếm vị trí chèn: Tương tự như thao tác tìm kiếm, bắt đầu từ nút gốc và lặp xuống phía dưới để tìm kiếm dựa trên mối quan hệ so sánh giữa giá trị của nút hiện tại và num, cho đến khi vượt qua nút lá (duyệt đến None) thì thoát khỏi vòng lặp.
Chèn nút tại vị trí đó: Tạo một nút mới cho num và đặt nó vào vị trí None đó.

Trong quá trình triển khai mã nguồn, cần lưu ý hai điểm sau:

Cây tìm kiếm nhị phân không cho phép các nút trùng lặp; nếu không, cây sẽ không còn thỏa mãn định nghĩa của nó nữa. Do đó, nếu nút cần chèn đã tồn tại trong cây, thao tác chèn sẽ bị bỏ qua và hàm sẽ trực tiếp trả về.
Để thực hiện việc chèn nút, chúng ta cần sử dụng nút pre để lưu lại nút ở lượt lặp trước đó. Bằng cách này, khi duyệt đến None, chúng ta có thể lấy được nút cha của nó, từ đó hoàn thành thao tác chèn nút.

[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{insert}

Tương tự như tìm kiếm nút, việc chèn nút cũng mất thời gian \(O(\log n)\).

Xóa nút¶

Đầu tiên, tìm nút mục tiêu trong cây tìm kiếm nhị phân, sau đó xóa nó. Tương tự như thao tác chèn nút, chúng ta cần đảm bảo rằng sau khi thao tác xóa hoàn thành, tính chất "cây con bên trái \(<\) nút gốc \(<\) cây con bên phải" của cây tìm kiếm nhị phân vẫn được duy trì. Do đó, tùy thuộc vào số lượng nút con mà nút mục tiêu có, chúng ta xét ba trường hợp: bậc (degree) là \(0\), \(1\) và \(2\), rồi thực hiện thao tác xóa tương ứng.

Như được hiển thị trong hình bên dưới, khi bậc của nút cần xóa là \(0\), điều đó có nghĩa là nút đó là nút lá (leaf node) và có thể trực tiếp xóa bỏ.

Như được hiển thị trong hình bên dưới, khi bậc của nút cần xóa là \(1\), chỉ cần thay thế nút cần xóa bằng nút con của nó là đủ.

Khi bậc của nút cần xóa là \(2\), chúng ta không thể trực tiếp xóa nó; thay vào đó, chúng ta cần sử dụng một nút khác để thay thế nó. Để duy trì tính chất "cây con bên trái \(<\) nút gốc \(<\) cây con bên phải" của cây tìm kiếm nhị phân, nút thay thế này có thể là nút nhỏ nhất trong cây con bên phải hoặc nút lớn nhất trong cây con bên trái.

Giả sử chúng ta chọn nút nhỏ nhất trong cây con bên phải, tức là nút kế tiếp trung thứ tự (inorder successor), quy trình xóa sẽ diễn ra như trong hình bên dưới.

Tìm nút kế tiếp của nút cần xóa trong "chuỗi duyệt trung thứ tự", ký hiệu là tmp.
Thay thế giá trị của nút cần xóa bằng giá trị của tmp, và xóa nút tmp trong cây một cách đệ quy.

<1><2><3><4>

Thao tác xóa nút cũng mất thời gian \(O(\log n)\), trong đó việc tìm nút cần xóa mất thời gian \(O(\log n)\), và việc lấy nút kế tiếp trung thứ tự (inorder successor node) mất thời gian \(O(\log n)\). Mã ví dụ như sau:

[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{remove}

Duyệt trung thứ tự có thứ tự¶

Như được hiển thị trong hình bên dưới, phép duyệt trung thứ tự (inorder traversal) của cây nhị phân tuân theo thứ tự duyệt "trái \(\rightarrow\) gốc \(\rightarrow\) phải", trong khi cây tìm kiếm nhị phân thỏa mãn mối quan hệ kích thước "nút con bên trái \(<\) nút gốc \(<\) nút con bên phải".

Điều này có nghĩa là khi thực hiện duyệt trung thứ tự trong cây tìm kiếm nhị phân, nút nhỏ tiếp theo luôn được duyệt trước, từ đó đem lại một tính chất quan trọng: Chuỗi duyệt trung thứ tự của cây tìm kiếm nhị phân là một chuỗi tăng dần.

Sử dụng tính chất chuỗi duyệt trung thứ tự tăng dần này, chúng ta có thể thu được dữ liệu có thứ tự trong cây tìm kiếm nhị phân chỉ trong thời gian \(O(n)\) mà không cần thêm thao tác sắp xếp nào khác, điều này vô cùng hiệu quả.

Hiệu suất của cây tìm kiếm nhị phân¶

Cho một tập hợp dữ liệu, chúng ta cân nhắc việc sử dụng mảng hoặc cây tìm kiếm nhị phân để lưu trữ. Quan sát bảng dưới đây, tất cả các thao tác trong cây tìm kiếm nhị phân đều có độ phức tạp thời gian dạng logarit, mang lại hiệu suất ổn định và hiệu quả. Mảng chỉ hiệu quả hơn cây tìm kiếm nhị phân trong các trường hợp có thao tác thêm với tần suất cao nhưng thao tác tìm kiếm và xóa với tần suất thấp.

Bảng So sánh hiệu suất giữa mảng và cây tìm kiếm

	Mảng chưa sắp xếp	Cây tìm kiếm nhị phân
Tìm kiếm phần tử	\(O(n)\)	\(O(\log n)\)
Chèn phần tử	\(O(1)\)	\(O(\log n)\)
Xóa phần tử	\(O(n)\)	\(O(\log n)\)

Trong trường hợp lý tưởng, cây tìm kiếm nhị phân là cân bằng, do đó mọi nút đều có thể được tìm thấy trong vòng \(O(\log n)\) lần lặp.

Tuy nhiên, nếu chúng ta liên tục chèn và xóa các nút trong cây tìm kiếm nhị phân, nó có thể bị suy biến thành một danh sách liên kết như hình dưới đây, khi đó độ phức tạp thời gian của các thao tác khác nhau cũng bị giảm xuống thành \(O(n)\).

Các ứng dụng phổ biến của cây tìm kiếm nhị phân¶

Được sử dụng làm các chỉ mục nhiều cấp (multi-level indexes) trong các hệ thống để triển khai các thao tác tìm kiếm, chèn và xóa hiệu quả.
Làm cấu trúc dữ liệu nền tảng cho một số thuật toán tìm kiếm nhất định.
Được sử dụng để lưu trữ các luồng dữ liệu (data streams) nhằm duy trì trạng thái có thứ tự của chúng.