a) Việc tìm kiếm trên cây tìm kiếm nhị phân là nhanh nhất khi cây là cây nhị phân cân bằng. Trong trường hợp này, mỗi lần tìm kiếm sẽ loại bỏ một nửa các nút cần xem xét, giảm đáng kể số lượng nút cần duyệt để tìm kiếm một giá trị.

b) Việc tìm kiếm trên cây tìm kiếm nhị phân là chậm nhất khi cây không cân bằng, đặc biệt là khi cây trở thành một danh sách liên kết. Trong trường hợp này, mỗi lần tìm kiếm chỉ loại bỏ một nút duy nhất và phải duyệt qua tất cả các nút trong cây để tìm kiếm giá trị cần tìm.

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

Thay đổi thứ tự chèn các phần tử vào cây nhị phân có tạo ra các cây tìm kiếm nhị phân khác nhau.

Ví dụ: 

Thứ tự chèn {3, 1, 2}:

Nếu dãy số được chèn vào cây tìm kiếm nhị phân là tăng dần (hoặc giảm dần), thì cây tìm kiếm nhị phân tương ứng sẽ có dạng như một cây cân bằng.

Sử dụng một cây tìm kiếm nhị phân (Binary Search Tree - BST) để lưu trữ và thao tác với danh sách học sinh và điểm trung bình của họ. Chương trình sẽ bao gồm các chức năng sau:

1.    Đọc dữ liệu đầu vào từ tệp Data.inp.

2.    Thêm học sinh mới vào cây tìm kiếm nhị phân.

3.    Tìm kiếm học sinh theo tên và đưa ra điểm trung bình của họ.

4.    Chương trình kết thúc khi nhập vào một chuỗi rỗng.

Dưới đây là hướng dẫn các bước triển khai chi tiết:

* Bước 1: Định nghĩa cấu trúc của cây tìm kiếm nhị phân

Chúng ta sẽ tạo một lớp Node để biểu diễn mỗi nút trong cây và một lớp BinarySearchTree để thực hiện các thao tác trên cây.

class Node:

    def __init__(self, name, score):

        self.name = name

        self.score = score

        self.left = None

        self.right = None

class BinarySearchTree:

    def __init__(self):

        self.root = None

    def insert(self, name, score):

        new_node = Node(name, score)

        if self.root is None:

            self.root = new_node

        else:

            self._insert(self.root, new_node)

    def _insert(self, current, new_node):

        if new_node.name < current.name:

            if current.left is None:

                current.left = new_node

            else:

                self._insert(current.left, new_node)

        elif new_node.name > current.name:

            if current.right is None:

                current.right = new_node

            else:

                self._insert(current.right, new_node)

    def search(self, name):

        return self._search(self.root, name)

    def _search(self, current, name):

        if current is None:

            return None

        if name == current.name:

            return current

        elif name < current.name:

            return self._search(current.left, name)

        else:

            return self._search(current.right, name)

* Bước 2: Đọc dữ liệu từ tệp Data.inp và khởi tạo cây tìm kiếm nhị phân

def load_data(filename):

    bst = BinarySearchTree()

    with open(filename, 'r', encoding='utf8') as file:

        for line in file:

            parts = line.strip().split(maxsplit=1)

            name = parts[0] + " " + parts[1]

            score = float(parts[2])

            bst.insert(name, score)

    return bst

bst = load_data("Data.inp")

* Bước 3: Thực hiện các thao tác thêm học sinh và tìm kiếm

def main():

    bst = load_data("Data.inp")

    while True:

        print("Chọn thao tác:")

        print("1. Thêm học sinh")

        print("2. Tìm kiếm học sinh")

        print("Nhập chuỗi rỗng để kết thúc chương trình.")

        choice = input("Nhập lựa chọn: ").strip()

        if choice == "":

            break

        elif choice == "1":

            name = input("Nhập họ tên học sinh: ").strip()

            if name == "":

                break

            try:

                score = float(input("Nhập điểm trung bình: ").strip())

                bst.insert(name, score)

                print(f"Đã thêm học sinh {name} với điểm trung bình {score}")

            except ValueError:

                print("Điểm trung bình phải là một số.")

        elif choice == "2":

            name = input("Nhập họ tên học sinh cần tìm: ").strip()

            if name == "":

                break

            result = bst.search(name)

            if result:

                print(f"Học sinh: {result.name}, Điểm trung bình: {result.score}")

            else:

                print("Không tìm thấy học sinh này.")

        else:

            print("Lựa chọn không hợp lệ. Vui lòng chọn lại.")

if __name__ == "__main__":

    main()

*Giải thích:

1. Cấu trúc cây tìm kiếm nhị phân:

- Node: Lớp biểu diễn một nút trong cây, bao gồm tên học sinh, điểm trung bình, và các nút con trái/phải.

- BinarySearchTree: Lớp chứa các phương thức để chèn (insert) và tìm kiếm (search) các nút trong cây.

2. Đọc dữ liệu:

- load_data(filename): Hàm này đọc dữ liệu từ tệp Data.inp và chèn từng học sinh vào cây tìm kiếm nhị phân.

3. Thao tác thêm và tìm kiếm:

- main(): Hàm chính thực hiện vòng lặp để cho phép người dùng thêm học sinh và tìm kiếm học sinh theo tên. Khi nhập vào chuỗi rỗng, chương trình sẽ kết thúc.

Để viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy, chương trình sẽ cần một phương thức đệ quy để thực hiện việc chèn. Dưới đây là cách triển khai mẫu:

class Node:

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

def insert_recursive(root, key):

    # Nếu cây là rỗng, tạo một nút mới và trả về

    if root is None:

        return Node(key)

    # Nếu khoá nhỏ hơn khoá của nút hiện tại, chèn vào cây con bên trái

    if key < root.key:

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

    # Nếu khoá lớn hơn hoặc bằng khoá của nút hiện tại, chèn vào cây con bên phải

    else:

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

    return root

# Hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy

def insert_into_binary_search_tree(T, v):

    T = insert_recursive(T, v)

    return T

# Ví dụ minh họa

if __name__ == "__main__":

    # Tạo một cây tìm kiếm nhị phân

    root = Node(5)

    root.left = Node(3)

    root.right = Node(8)

    root.left.left = Node(2)

    root.left.right = Node(4)

    root.right.left = Node(6)

    root.right.right = Node(9)

    # In cây tìm kiếm nhị phân trước khi chèn

    print("Cây tìm kiếm nhị phân trước khi chèn:")

    def inorder_traversal(node):

        if node:

            inorder_traversal(node.left)

            print(node.key, end=" ")

            inorder_traversal(node.right)

    inorder_traversal(root)

    print()

    # Chèn khoá 7 vào cây tìm kiếm nhị phân

    insert_into_binary_search_tree(root, 7)

    # In cây tìm kiếm nhị phân sau khi chèn

    print("Cây tìm kiếm nhị phân sau khi chèn:")

    inorder_traversal(root)

* Chú thích:

- Node là lớp biểu diễn một nút trong cây tìm kiếm nhị phân.

- insert_recursive là hàm đệ quy để chèn một khoá mới vào cây tìm kiếm nhị phân.

- insert_into_binary_search_tree là hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy.

Để kiểm tra xem một dãy đã cho có phải là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi hay không, chúng ta có thể sử dụng một số quy tắc sau:\

- Dãy đó phải là biểu diễn của một cây nhị phân, tức là mỗi phần tử của dãy đều có thể là một nút hoặc None.

- Đối với mỗi nút trong dãy, nút trái của nó (nếu có) phải nằm ở vị trí 2*i + 1 trong dãy, và nút phải của nó (nếu có) phải nằm ở vị trí 2*i + 2 trong dãy, với i là vị trí của nút trong dãy (bắt đầu từ 0).

Dựa trên các quy tắc trên có thể viết chương trình như sau:

def is_complete_binary_tree(arr):

    # Kiểm tra dãy có phải là biểu diễn của một cây nhị phân không

    for i in range(len(arr)):

        if arr[i] is not None:

            # Kiểm tra nếu nút trái không vượt quá độ dài của dãy

            left_child_index = 2 * i + 1

            if left_child_index < len(arr) and arr[left_child_index] is None:

                return False

            # Kiểm tra nếu nút phải không vượt quá độ dài của dãy

            right_child_index = 2 * i + 2

            if right_child_index < len(arr) and arr[right_child_index] is None:

                return False

    return True

# Ví dụ

arr1 = [10, 7, 0, 5, None, 3]

arr2 = [1, 6, None, 2, 3, None, 4]

if is_complete_binary_tree(arr1):

    print("Dãy arr1 là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")

else:

    print("Dãy arr1 không là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")

if is_complete_binary_tree(arr2):

    print("Dãy arr2 là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")

else:

    print("Dãy arr2 không là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")

Để kiểm tra xem một dãy đã cho có phải là biểu diễn của một cây tìm kiếm nhị phân hay không, có thể sử dụng một thuật toán kiểm tra tính chất của cây tìm kiếm nhị phân.

Một cây tìm kiếm nhị phân có tính chất sau:

• Mỗi nút trong cây có giá trị lớn hơn hoặc bằng tất cả các nút trong cây con bên trái của nó.
• Mỗi nút trong cây có giá trị nhỏ hơn tất cả các nút trong cây con bên phải của nó.

Dựa trên các tính chất trên chương trình sẽ được viết như sau:

class TreeNode:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

def is_binary_search_tree(arr):

    def helper(index, min_val, max_val):

        if index >= len(arr) or arr[index] is None:

            return True

        if min_val < arr[index] < max_val:

            left_child_index = 2 * index + 1

            right_child_index = 2 * index + 2

            return (helper(left_child_index, min_val, arr[index]) and

                    helper(right_child_index, arr[index], max_val))

        else:

            return False

    return helper(0, float('-inf'), float('inf'))

# Ví dụ

arr1 = [5, 3, 6, None, 4, None, 10]

arr2 = [2, 1, 5, None, 3, 4, 10]

if is_binary_search_tree(arr1):

    print("Dãy arr1 là biểu diễn của một cây tìm kiếm nhị phân.")

else:

    print("Dãy arr1 không là biểu diễn của một cây tìm kiếm nhị phân.")

if is_binary_search_tree(arr2):

    print("Dãy arr2 là biểu diễn của một cây tìm kiếm nhị phân.")

else:

    print("Dãy arr2 không là biểu diễn của một cây tìm kiếm nhị phân.")