Giải SGK Chuyên đề Tin học 12 Bài 9. Các thuật toán duyệt trên cây tìm kiếm nhị phân

a) Nút đầu tiên: Khi thực hiện thuật toán duyệt giữa, nút đầu tiên được duyệt là nút ‘1’, vì nó là nút nằm xa nhất về bên trái của cây.

b) Nút cuối cùng: Nút cuối cùng được duyệt là nút ‘19’, vì nó là nút nằm xa nhất về bên phải của cây.

c) Thứ tự duyệt: Các nút sẽ được duyệt theo thứ tự sau: 1, 3, 4, 7, 8, 9, 10, 12, 15, 14, 19. Kết quả này cho thấy thuật toán duyệt giữa trên cây tìm kiếm nhị phân sẽ cho ra danh sách các nút theo thứ tự tăng dần. Điều này xảy ra bởi vì thuật toán này luôn tuân theo quy tắc: trước tiên duyệt tất cả các nút nhỏ hơn nút gốc (bên trái), sau đó là nút gốc (ở giữa), và cuối cùng là tất cả các nút lớn hơn nút gốc (bên phải).

Ý nghĩa của các thuật toán duyệt trên cây tìm kiếm nhị phân:

- Duyệt trước: Dùng để sao chép cây, tính toán giá trị các nút trong trường hợp biểu thức toán học cây biểu thức, hay xử lý cây trong nhiều ứng dụng khác.

- Duyệt giữa: Đặc biệt hữu ích cho BST vì nó trả về các giá trị theo thứ tự tăng dần. Đây là lý do tại sao in-order traversal được sử dụng phổ biến trong các ứng dụng yêu cầu dữ liệu có thứ tự.

- Duyệt sau: Thường dùng trong việc xóa cây hoặc giải phóng bộ nhớ vì nó đảm bảo rằng một nút chỉ được thăm sau khi các cây con của nó đã được xử lý.

Sự khác biệt giữa các thuật toán duyệt trên cây tìm kiếm nhị phân (trong BST) so với cây nhị phân đã học ở bài 6 ( cây nhị phân hoàn chỉnh):

- Khi duyệt BST biểu diễn bằng mảng, cần kiểm tra thêm điều kiện k < len(T) và T[k] is not None để tránh xử lý các nút giả None, đảm bảo không thăm các nút không tồn tại.

- Các thuật toán duyệt cơ bản không thay đổi về bản chất, nhưng cần chú ý đến việc xử lý các nút giả để tránh lỗi ngoài ý muốn.

Các bước xây dựng cây tìm kiếm nhị phân (BST) từ dãy số A

- Chèn 2: Làm gốc của cây.

- Chèn 1: So với 2, 1 nhỏ hơn, chèn vào bên trái của 2.

- Chèn 9: So với 2, 9 lớn hơn, chèn vào bên phải của 2.

- Chèn 0: So với 2, nhỏ hơn; so với 1, nhỏ hơn, chèn vào bên trái của 1.

- Chèn 2 (thứ hai): So với 2, bằng nhau; theo quy tắc chung (trường hợp đặc biệt), chèn vào bên phải của 2 gốc

- Chèn 1 (thứ hai): So với 2, nhỏ hơn; so với 1, bằng nhau; chèn vào bên phải của 1.

- Chèn 5: So với 2, lớn hơn; so với 9, nhỏ hơn, chèn vào bên trái của 9.

Cấu trúc cây BST

Hướng dẫn cụ thể các bước thực hiện như sau:

1. Duyệt cây con phải của nút gốc (2):

- Duyệt cây con phải của nút 9 (không có nút con phải nào).

- Thăm nút 9.

- Duyệt cây con trái của nút 9:

Duyệt cây con phải của nút 5 (không có nút con phải nào).

Thăm nút 5.

Duyệt cây con trái của nút 5 (không có nút con trái nào).

2. Thăm nút gốc (2).

3. Duyệt cây con trái của nút gốc (2):

Duyệt cây con phải của nút 1:

- Duyệt cây con phải của nút 1 (thứ hai) (không có nút con phải nào).

- Thăm nút 1 (thứ hai).

- Duyệt cây con trái của nút 1 (thứ hai) (không có nút con trái nào).

Thăm nút 1.

Duyệt cây con trái của nút 1:

- Duyệt cây con phải của nút 0 (không có nút con phải nào).

- Thăm nút 0.

- Duyệt cây con trái của nút 0 (không có nút con trái nào).

Kết quả duyệt ngược

9, 5, 2, 2, 1, 1, 0

Như vậy, dãy các khoá theo thứ tự duyệt ngược trên cây tìm kiếm nhị phân được tạo từ dãy A = [2,1,9,0,2,1,5] là: [9, 5, 2, 2, 1, 1, 0].

Để sắp xếp dãy số A theo thứ tự tăng dần hoặc giảm dần, chúng ta có thể sử dụng nhiều thuật toán sắp xếp khác nhau. Một trong những phương pháp hiệu quả và dễ hiểu là sử dụng cây tìm kiếm nhị phân (BST) để sắp xếp dãy số.

Ý tưởng thuật toán

1. Chèn các phần tử của dãy A vào cây tìm kiếm nhị phân (BST).

2. Duyệt cây theo thứ tự tăng dần hoặc giảm dần để lấy ra các phần tử đã được sắp xếp.

Thuật toán chi tiết:

1. Chèn các phần tử vào BST

Mỗi phần tử trong dãy A sẽ được chèn vào BST theo quy tắc:

- Nếu phần tử nhỏ hơn nút hiện tại, chuyển sang cây con trái.

- Nếu phần tử lớn hơn hoặc bằng nút hiện tại, chuyển sang cây con phải.

2. Duyệt cây để lấy ra dãy đã sắp xếp

- Duyệt giữa (In-order Traversal): để lấy các phần tử theo thứ tự tăng dần.

- Duyệt ngược (Reverse in-order Traversal): để lấy các phần tử theo thứ tự giảm dần.

Nhận xét:

- Hiệu quả: Thuật toán sử dụng BST có thời gian chèn và tìm kiếm trung bình là O(log⁡n)O(\log n)O(logn) khi cây cân bằng, và O(n)O(n)O(n) trong trường hợp xấu nhất khi cây trở thành đường thẳng (skewed tree).

- Tính chất: BST duy trì các phần tử theo thứ tự, do đó việc duyệt cây sẽ cho ra dãy số đã được sắp xếp.

- Ứng dụng: Thuật toán này không phù hợp cho các trường hợp cần sắp xếp nhanh và hiệu quả như QuickSort hoặc MergeSort (có độ phức tạp O(nlog⁡n)O(n \log n)O(nlogn)), nhưng nó giúp minh họa tốt về cách sử dụng cấu trúc cây trong việc sắp xếp dữ liệu.

1. Định nghĩa cấu trúc nút cây BST:

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

2. Hàm chèn một phần tử vào BST

def insert(root, key):

    if root is None:

        return TreeNode(key)

    else:

        if root.val < key:

            root.right = insert(root.right, key)

        else:

            root.left = insert(root.left, key)

    return root

3. Hàm duyệt giữa để lấy thứ tự tăng dần

def in_order_traversal(root, result):

    if root:

        in_order_traversal(root.left, result)

        result.append(root.val)

        in_order_traversal(root.right, result)

4. Hàm chính để sắp xếp dãy A

def BSTSort(A):

    if not A:

        return []

    # Bước 1: Tạo cây tìm kiếm nhị phân từ dãy A

    root = None

    for key in A:

        root = insert(root, key)

    # Bước 2: Duyệt cây để lấy kết quả sắp xếp

    sorted_result = []

    in_order_traversal(root, sorted_result)

    return sorted_result