Câu hỏi:

13/07/2024 502

Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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

Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào. (ảnh 1)

Duyệt giữa (In-order Traversal)

Duyệt giữa trên cây tìm kiếm nhị phân là duyệt theo thứ tự cây con trái, nút gốc, cây con phải.

Cụ thể các bước thực hiện như sau:

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

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

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

+ Thăm nút 1.

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

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

- Thăm nút 1.

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

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

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

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

- Thăm nút 9.

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

Kết quả duyệt giữa

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

Như vậy, dãy các khoá theo thứ tự duyệt giữa 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à: [0, 1, 1, 2, 2, 5, 9].

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân (BST) có độ phức tạp thời gian phụ thuộc vào cấu trúc của cây BST trong quá trình chèn và duyệt các phần tử.

Độ phức tạp thời gian của thuật toán sắp xếp bằng BST

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

- Trung bình: Đối với cây BST cân bằng, độ sâu trung bình của cây là O(log⁡n)O(\log n)O(logn), do đó, việc chèn mỗi phần tử có độ phức tạp trung bình là O(log⁡n)O(\log n)O(logn).

- Trường hợp xấu nhất: Trong trường hợp xấu nhất, nếu cây BST trở thành một cây một nhánh (giống như danh sách liên kết) khi các phần tử được chèn theo thứ tự tăng hoặc giảm dần, độ sâu của cây sẽ là O(n)O(n)O(n). Vì vậy, việc chèn mỗi phần tử có độ phức tạp là O(n)O(n)O(n).

2. Duyệt cây để lấy các phần tử đã sắp xếp:

- Việc duyệt cây (in-order hoặc reverse in-order) có độ phức tạp là O(n)O(n)O(n) vì chúng ta phải thăm tất cả các nút trong cây một lần.

Tổng độ phức tạp thời gian

- Trung bình: Trong trường hợp trung bình khi cây BST gần như cân bằng, độ phức tạp cho việc chèn n phần tử là O(nlog⁡n)O(n \log n)O(nlogn), và duyệt cây là O(n)O(n)O(n). Do đó, tổng độ phức tạp thời gian là O(nlog⁡n)O(n \log n)O(nlogn).

- Trường hợp xấu nhất: Trong trường hợp xấu nhất khi cây BST trở thành một cây một nhánh, độ phức tạp cho việc chèn n phần tử là O(n2)O(n^2)O(n2), và duyệt cây là O(n)O(n)O(n). Do đó, tổng độ phức tạp thời gian là O(n2)O(n^2)O(n2).

Kết luận

- Trung bình: O(nlog⁡n)O(n \log n)O(nlogn)

- Trường hợp xấu nhất: O(n2)O(n^2)O(n2)

Để tránh trường hợp xấu nhất, các thuật toán như AVL tree hoặc Red-Black tree có thể được sử dụng để đảm bảo rằng cây BST luôn gần như cân bằng, giữ độ phức tạp thời gian ở mức O(nlog⁡n)O(n \log n)O(nlogn) trong mọi trường hợp.

Lời giải

Để tính chiều cao của cây tìm kiếm nhị phân (BST), chúng ta có thể sử dụng phương pháp đệ quy. Chiều cao của một cây BST là độ dài của đường dẫn từ nút gốc đến nút lá xa nhất. Dưới đây là cài đặt Python cho hàm height(T) để tính chiều cao của cây tìm kiếm nhị phân T.

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

def height(T):

    if T is None:

        return -1  # Chiều cao của một cây rỗng là -1

    else:

        # Tính chiều cao của cây con bên trái và cây con bên phải

        left_height = height(T.left)

        right_height = height(T.right)

        # Chiều cao của cây là chiều cao lớn nhất của hai cây con cộng thêm 1

        return max(left_height, right_height) + 1

Giải thích:

- Hàm height(T) sẽ tính chiều cao của cây tìm kiếm nhị phân T bằng cách sử dụng đệ quy.

- Nếu cây T là cây rỗng (None), chiều cao của cây là -1.

- Nếu cây T không rỗng, chúng ta tính chiều cao của cây con bên trái và cây con bên phải.

- Chiều cao của cây là chiều cao lớn nhất của hai cây con cộng thêm 1 (chiều cao của nút gốc).

 

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP