Cây tìm kiếm nhị phân (BST-Binary Search Tree)

1. Cây nhị phân và Cây tìm kiếm nhị phân là gì ?

Trong bài này chúng ta sẽ tìm hiểu về một cấu trúc dữ liệu cây đặc biệt, là cây nhị phân, và sau đó, một cấu trúc cây nhị phân đặc biệt, là cây tìm kiếm nhị phân.

Cây nhị phân là một cấu trúc dữ liệu cây mà mỗi nút có tối đa hai nút con, được gọi là nút trái và nút phải.

Cây tìm kiếm nhị phân, đôi khi được gọi là cây nhị phân được sắp xếp, là cây nhị phân mà mỗi nút đều được gắn một khóa sao cho với mọi nút, khóa của nút đó phải lớn hơn hoặc bằng mọi khóa nằm ở cây con bên trái nếu có, và nhỏ hơn hoặc bằng mọi khóa nằm ở cây con bên phải nếu có.

Cây tìm kiếm nhị phân được viết tắt là BST.

Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tìm kiếm trở nên phức tạp hơn.

Cây tìm kiếm nhị phân kết hợp được khả năng tìm kiếm nhanh của thuật toán sorted search trên danh sách có thứ tự, và khả năng chèn sửa xóa nhanh chóng của danh sách liên kết.

2. Biểu diễn cây tìm kiếm nhị phân (BST)

Mỗi một nút trong BST đều có một khóa và giá trị liên kết với nó. Trong khi tìm kiếm, khóa cần tìm được so sánh với các khóa trong cây tìm kiếm nhị phân (BST) và nếu tìm thấy, giá trị liên kết sẽ được thu nhận.

Ví dụ một cây tìm kiếm nhị phân (BST):

Từ hình ví dụ minh họa trên ta thấy rằng, khóa của nút gốc có giá trị 27 và tất cả khóa bên trái của cây con bên trái đều có giá trị nhỏ hơn 27 này và tất cả các khóa bên phải của cây con bên phải đều có giá trị lớn hơn 27.

3. Hoạt động cơ bản trên cây tìm kiếm nhị phân

Dưới đây là một số hoạt động cơ bản có thể được thực hiện trên cây tìm kiếm nhị phân:

• Hoạt động tìm kiếm: tìm kiếm một phần tử trong một cây.
• Hoạt động chèn: chèn một phần tử vào trong một cây.
• Hoạt động duyệt tiền thứ tự: duyệt một cây theo cách thức duyệt tiền thứ tự.
• Hoạt động duyệt trung thứ tự: duyệt một cây theo cách thứ duyệt trung thứ tự.
• Hoạt động duyệt hậu thứ tự: duyệt một cây theo cách thức duyệt hậu thứ tự.

3.1 Nút (Node) trong cây tìm kiếm nhị phân

Một nút có một vài dữ liệu, tham chiếu tới các nút con bên trái và nút con bên phải của nó.

public class TreeNode<E> {  protected E element;  protected TreeNode<E> left;  protected TreeNode<E> right;  public TreeNode(E e) {     element = e;  }}

3.2 Hoạt động tìm kiếm trong cây tìm kiếm nhị phân

Mỗi khi một phần tử được tìm kiếm: bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa (key), thì sẽ tìm phần tử ở cây con bên trái; nếu lớn hơn thì sẽ tìm phần tử ở cây con bên phải.

3.3 Hoạt động chèn trong cây tìm kiếm nhị phân

Mỗi khi một phần tử được chèn: đầu tiên chúng ta cần xác định vị trí chính xác của phần tử này. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa (key), thì tìm kiếm vị trí còn trống ở cây con bên trái và chèn dữ liệu vào đó; nếu dữ liệu là nhỏ hơn thì tìm kiếm vị trí còn sống ở cây con bên phải và chèn dữ liệu vào đó.

4. Duyệt cây trong cấu trúc dữ liệu và giải thuật

Duyệt cây là gì ?

Duyệt cây là một tiến trình để truy cập tất cả các nút của một cây và cũng có thể in các giá trị của các nút này. Bởi vì tất cả các nút được kết nối thông qua các cạnh (hoặc các link), nên chúng ta luôn luôn bắt đầu truy cập từ nút gốc. Do đó, chúng ta không thể truy cập ngẫu nhiên bất kỳ nút nào trong cây. Có ba phương thức mà chúng ta có thể sử dụng để duyệt một cây:

• Duyệt tiền thứ tự (Pre-order Traversal)
• Duyệt trung thứ tự (In-order Traversal)
• Duyệt hậu thứ tự (Post-order Traversal)

Nói chung, chúng ta duyệt một cây để tìm kiếm hay là để xác định vị trí phần tử hoặc khóa đã cho trong cây hoặc là để in tất cả giá trị mà cây đó chứa.

4.1 Duyệt trung thứ tự trong cây nhị phân

Trong cách duyệt này, cây con bên trái được truy cập đầu tiên, sau đó là nút gốc và sau đó là cây con bên phải. Bạn nên luôn luôn ghi nhớ rằng mỗi nút đều có thể biểu diễn một cây con.

Nếu một cây nhị phân được duyệt trung thứ tự, kết quả tạo ra sẽ là các giá trị khóa được sắp xếp theo thứ tự tăng dần.

Ở hình ví dụ minh họa trên, A là nút gốc. Với phương thức duyệt trung thứ tự, chúng ta bắt đầu từ nút gốc A, di chuyển tới cây con bên trái B của nút gốc. Tại đây, B cũng được duyệt theo cách thức duyệt trung thứ tự. Và tiến trình tiếp tục cho đến khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt trung thứ tự cho cây trên sẽ là:

D → B → E → A → F → C → G

Giải thuật cho cách duyệt trung thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:

Bước 1: Duyệt các cây con bên trái một cách đệ qui

Bước 2: Truy cập nút gốc

Bước 3: Duyệt các cây con bên phải một cách đệ qui

4.2 Duyệt tiền thứ tự trong cây nhị phân

Trong cách thức duyệt tiền thứ tự trong cây nhị phân, nút gốc được duyệt đầu tiên, sau đó sẽ duyệt cây con bên trái và cuối cùng sẽ duyệt cây con bên phải.

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách thức duyệt tiền thứ tự, đầu tiên chúng ta truy cập chính nút gốc A này và sau đó di chuyển tới nút con bên trái B của nó. B cũng được duyệt theo cách thức duyệt tiền thứ tự. Và tiến trình tiếp tục cho tới khi tất cả các nút đều đã được truy cập. Kết quả của cách thức duyệt tiền thứ tự cây này sẽ là:

A → B → D → E → C → F → G

Giải thuật cho cách duyệt tiền thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:

Bước 1: Truy cập nút gốc

Bước 2: Duyệt các cây con bên trái một cách đệ qui

Bước 3: Duyệt các cây con bên phải một cách đệ qui

4.3 Duyệt hậu thứ tự trong cây nhị phân

Trong cách thức duyệt hậu thứ tự trong cây nhị phân, nút gốc của cây sẽ được truy cập cuối cùng, do đó bạn cần chú ý. Đầu tiên, chúng ta duyệt cây con bên trái, sau đó sẽ duyệt cây con bên phải và cuối cùng là duyệt nút gốc. 

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách duyệt hậu thứ tự, đầu tiên chúng ta truy cập cây con bên trái B. B cũng được duyệt theo cách thứ duyệt hậu thứ tự. Và tiến trình sẽ tiếp tục tới khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt hậu thứ tự của cây con trên sẽ là:

D → E → B → F → G → C → A

Giải thuật cho cách duyệt hậu thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:

Bước 1: Duyệt các cây con bên trái một cách đệ qui

Bước 2: Duyệt các cây con bên phải một cách đệ qui

Bước 3: Truy cập nút gốc.