Trong các câu sau đây, câu nào là đúng về cây tìm kiếm nhị phân?

a) Trong cây tìm kiếm nhị phân, giả trị khóa mọi nút của cây con trái và cây con phải đều nhỏ hơn giá trị khóa của nút gốc

b) Từ một dãy số nguyên đương cho trước chỉ tạo được duy nhật một cây tìm kiếm nhị phân

c) Cây tìm kiếm nhị phân giúp quả trình tìm kiếm phần tử trong dãy có giá trị cho trước nhanh hơn

d) Quá trình tìm kiếm trên cây tìm kiếm nhị phân luôn cho kết quả là tìm được nút có giá trị bằng giá trị khoa học cho trước

Trong cây tìm kiếm nhị phân em vừa xây dựng ở phần vận dụng, để xác định số bước so sánh cần thiết để tìm ra một nút có giá trị khóa cụ thể trong cây tìm kiếm nhị phân, ta cần biết cấu trúc cụ thể của cây và vị trí của giá trị khóa đó trong cây. Ở bài toán tổng quát, số bước so sánh sẽ phụ thuộc vào chiều cao của cây.

Giả sử em có một cây tìm kiếm nhị phân (BST) và muốn tìm một giá trị khóa cụ thể k , quá trình tìm kiếm hoạt động như sau:

Bước 1. So sánh k với giá trị khóa của nút gốc.

Bước 2. Nếu k bằng giá trị khóa của nút gốc, ta đã tìm thấy giá trị và dừng lại.

Bước 3. Nếu k nhỏ hơn giá trị khóa của nút gốc, ta tiếp tục tìm kiếm trong cây con trái.

Bước 4. Nếu k lớn hơn giá trị khóa của nút gốc, ta tiếp tục tìm kiếm trong cây con phải.

Bước 5. Lặp lại các bước trên cho đến khi tìm thấy giá trị khóa k hoặc đi đến một nút lá (nút không có con), mà không tìm thấy k trong cây.

Số bước so sánh chính là số lần so sánh cần thiết để đi từ gốc cây đến nút chứa giá trị khóa k. Số bước này bằng độ sâu của nút chứa giá trị khóa k trong cây.

Trong trường hợp cây là một cây tìm kiếm nhị phân cân bằng, chiều cao của cây là (O(log n)), với n là số lượng nút trong cây. Do đó, số bước so sánh trung bình để tìm kiếm một giá trị khóa trong cây sẽ là (O(log n)).

Nếu cây không cân bằng, trong trường hợp xấu nhất (cây bị thoái hóa thành danh sách liên kết), số bước so sánh có thể lên tới (O(n)).

Ví dụ:

Giả sử có một cây tìm kiếm nhị phân với các giá trị khóa được chèn lần lượt như sau: 9, 5, 19, 3, 7, 15, 24.

Cây sẽ được xây dựng như sau:

Nếu em muốn tìm giá trị khóa 7 trong cây này, các bước so sánh sẽ là:

1. So sánh 7 với 9 (gốc): 7 < 9, đi đến cây con trái.

2. So sánh 7 với 5: 7 > 5, đi đến cây con phải.

3. So sánh 7 với 7: Đúng, đã tìm thấy giá trị khóa.

Vậy cần 3 bước so sánh để tìm giá trị khóa 7 trong cây này.

Danh sách giá trị khóa các nút ở cây nhị phân (Hình 1) trong phép duyệt cây theo thứ tự giữa như sau:

1. Bắt đầu từ gốc (2), duyệt cây con trái của 2.

2. Cây con trái của 2 là 1, không có cây con trái và cây con phải. Thăm nút 1.

3. Trở lại nút gốc 2, thăm nút 2.

4. Duyệt cây con phải của 2 là 5.

5. Từ 5, duyệt cây con trái của 5 là 3.

6. Cây con trái của 3 là null, thăm nút 3.

7. Duyệt cây con phải của 3 là 4.

8. Cây con trái và cây con phải của 4 đều là null. Thăm nút 4.

9. Trở lại nút 5, thăm nút 5.

10. Duyệt cây con phải của 5 là 6, không có cây con trái và cây con phải. Thăm nút 6.

Danh sách giá trị khóa các nút theo thứ tự giữa là: 1, 2, 3, 4, 5, 6

Nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra:

- Điều này phù hợp với đặc điểm của cây tìm kiếm nhị phân (BST). Trong cây tìm kiếm nhị phân, khi duyệt theo thứ tự giữa, các giá trị khóa luôn được liệt kê theo thứ tự tăng dần.

- Danh sách giá trị khóa được duyệt theo thứ tự giữa (In-order Traversal) của cây nhị phân này là một dãy các giá trị tăng dần.

- Như vậy, cây nhị phân này cũng là một cây tìm kiếm nhị phân.