Chuyên đề Tin học 12 Bài 3 (Cánh diều): Cây tìm kiếm nhị phân

Giải Chuyên đề Tin học 12 Bài 3: Cây tìm kiếm nhị phân

Khởi động trang 43 Chuyên đề Tin học 12: Em hãy đưa ra 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 và nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra này.

Lời giải:

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.

Hoạt động 1 trang 43 Chuyên đề Tin học 12: An và Hòa cùng tham gia một hoạt động về bài toán trên dãy số. Giả sử các phần từ 45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58 của tập số An giữ được biểu diễn dưới dạng cây nhị phân trong Hình 2, các nút được đánh chỉ số từ 0 đến 11. Em hãy quan sát đặc điểm của cây và các giá trị khóa từng nút của cây này, tử đó đưa ra một cách giúp Hoa đạt ít câu hỏi nhất cô thế để tim ra vị trí nút có giá trị khoá 55.

Lời giải:

An và Hòa cùng tham gia một hoạt động về bài toán trên dãy số. Giả sử các phần từ 45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58 của tập số An giữ được biểu diễn dưới dạng cây nhị phân trong Hình 2, các nút được đánh chỉ số từ 0 đến 11. Hướng dẫn các bước xây dựng cây BST từ dãy số [45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58]:

1. Bắt đầu với 45 là gốc.

2. Chèn 35: 35 < 45, nên 35 là con trái của 45.

3. Chèn 60: 60 > 45, nên 60 là con phải của 45.

4. Chèn 30: 30 < 45 và 30 < 35, nên 30 là con trái của 35.

5. Chèn 46: 46 > 45 và 46 < 60, nên 46 là con trái của 60.

6. Chèn 75: 75 > 45 và 75 > 60, nên 75 là con phải của 60.

7. Chèn 11: 11 < 45 và 11 < 35 và 11 < 30, nên 11 là con trái của 30.

8. Chèn 55: 55 > 45 và 55 < 60 và 55 > 46, nên 55 là con phải của 46.

9. Chèn 65: 65 > 45 và 65 > 60 và 65 < 75, nên 65 là con trái của 75.

10. Chèn 96: 96 > 45 và 96 > 60 và 96 > 75, nên 96 là con phải của 75.

11. Chèn 12: 12 < 45 và 12 < 35 và 12 < 30 và 12 > 11, nên 12 là con phải của 11.

12. Chèn 58: 58 > 45 và 58 < 60 và 58 > 46 và 58 > 55, nên 58 là con phải của 55.

Cây BST sẽ có cấu trúc như sau:

Thực hiện theo các bước sau để tìm giá trị khóa 55,

1. So sánh với nút gốc (45):

• 55 > 45: đi tới cây con phải (60).

2. So sánh với nút 60:

• 55 < 60: đi tới cây con trái (46).

3. So sánh với nút 46:

• 55 > 46: đi tới cây con phải (55).

4. So sánh với nút 55:

55 = 55: tìm thấy giá trị khóa.

Vậy, chỉ cần 4 bước so sánh để tìm ra nút có giá trị khóa 55 trong cây này.

Thực hành trang 45 Chuyên đề Tin học 12: Từ cây tìm kiểm nhị phân trong Hình 3 sau khi đã chèn thêm nút có giá trị khóa 33, em hãy mô tả từng bước chèn một nút mới có giá trị khóa bằng 28 vào cây.

Lời giải:

Các bước để chèn một nút mới có giá trị khóa bằng 28 vào cây tìm kiếm nhị phân:

- Bước 1: So sánh giá trị khóa 28 với nút gốc (có giá trị khóa là 21). Vì 28 lớn hơn 21, ta di chuyển sang nút con bên phải của nút gốc.

- Bước 2: So sánh giá trị khóa 28 với nút con phải của nút gốc (có giá trị khóa là 36). Vì 28 nhỏ hơn 36, ta di chuyển sang nút con bên trái của nút này.

- Bước 3: Nút con bên trái của nút có giá trị khóa 36 không tồn tại, do đó chèn nút mới có giá trị khóa 28 làm nút con bên trái của nút có giá trị khóa 36.

Kết luận: Nút mới có giá trị khóa 28 sẽ được chèn vào vị trí là nút con bên trái của nút có giá trị khóa 36 trong cây.

Thực hành trang 47 Chuyên đề Tin học 12: Từ cây tìm kiểm nhị phân trong Hình 5, em hãy mô tả từng bước tìm kiểm một nút có giá trị khóá bằng 65 và một nút có giá trị khoá bằng 70 trên cây.

Lời giải:

Từ cây tìm kiểm nhị phân trong Hình 5, em hãy mô tả từng bước tìm kiểm một nút có giá trị khóá bằng 65 và một nút có giá trị khoá bằng 70 trên cây như sau:

- Bước 1: So sánh giá trị khóa 65 với nút gốc (giả sử là nút có giá trị khóa X). Nếu 65 lớn hơn X, di chuyển sang nút con bên phải của nút gốc.

- Bước 2: Tiếp tục so sánh giá trị khóa 65 với nút con bên phải (giả sử là nút có giá trị khóa Y). Nếu 65 lớn hơn Y, di chuyển sang nút con bên phải của nút này.

- Bước 3: Lặp lại quá trình so sánh cho đến khi tìm thấy nút có giá trị khóa 65 hoặc đến nút lá mà không tìm thấy (nút không có con bên phải hoặc trái phù hợp).

Đối với việc tìm kiếm nút có giá trị khóa bằng 70, quy trình tương tự như trên sẽ được áp dụng. Nếu không tìm thấy nút nào có giá trị khóa 70, điều này có nghĩa là nút đó không tồn tại trong cây.

Vận dụng trang 48 Chuyên đề Tin học 12: Từ một dãy có ít nhất 6 số nguyên dương tùy ý em hãy vẽ hình minh hoa và mô tả từng bước xây dựng một cây tìm kiếm nhị phân tương ứng với dãy đó, bắt dầu từ cây rỗng.

Lời giải:

Hướng dẫn gợi ý các bước làm:

Để minh họa cách xây dựng một cây tìm kiếm nhị phân (BST - Binary Search Tree) từ một dãy số nguyên dương tùy ý, hãy xem xét dãy số ví dụ: [10, 5, 15, 3, 7, 12, 18]. Ta có các bước chi tiết để xây dựng BST từ dãy số trên, bắt đầu từ cây rỗng:

Bước 1: Khởi tạo cây rỗng

Lúc đầu, cây tìm kiếm nhị phân (BST) là rỗng.

Bước 2: Thêm phần tử đầu tiên

- Phần tử 10: Là phần tử đầu tiên trong dãy, sẽ là gốc của cây.

Bước 3: Thêm phần tử thứ hai

- Phần tử 5: So sánh với gốc 10. Vì 5 < 10, nên 5 sẽ là con trái của 10.

Bước 4: Thêm phần tử thứ ba

- Phần tử 15: So sánh với gốc 10. Vì 15 > 10, nên 15 sẽ là con phải của 10.

Bước 5: Thêm phần tử thứ tư

- Phần tử 3: So sánh với gốc 10, sau đó với 5. Vì 3 < 10 và 3 < 5, nên 3 sẽ là con trái của 5.

Bước 6: Thêm phần tử thứ năm

- Phần tử 7: So sánh với gốc 10, sau đó với 5. Vì 7 < 10 và 7 > 5, nên 7 sẽ là con phải của 5.

Bước 7: Thêm phần tử thứ sáu

- Phần tử 12: So sánh với gốc 10, sau đó với 15. Vì 12 > 10 và 12 < 15, nên 12 sẽ là con trái của 15.

Bước 8: Thêm phần tử thứ bảy

- Phần tử 18: So sánh với gốc 10, sau đó với 15. Vì 18 > 10 và 18 > 15, nên 18 sẽ là con phải của 15.

Câu hỏi tự kiểm tra 1 trang 48 Chuyên đề Tin học 12: 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

Lời giải:

Đáp án đúng là 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.

Các câu còn lại sai vì:

a) Sai vì trong cây tìm kiếm nhị phân, giá trị khóa của mọi nút trong cây con trái phải nhỏ hơn giá trị khóa của nút gốc, và giá trị khóa của mọi nút trong cây con phải phải lớn hơn giá trị khóa của nút gốc.

b) Sai vì từ một dãy số nguyên cho trước có thể tạo ra nhiều cây tìm kiếm nhị phân khác nhau tùy thuộc vào thứ tự chèn các số vào cây.

d) Sai vì quá trình tìm kiếm trên cây tìm kiếm nhị phân không luôn luôn cho kết quả tìm được nút có giá trị bằng giá trị khóa cho trước, nó chỉ trả về kết quả nếu giá trị đó thực sự tồn tại trong cây.

Câu hỏi tự kiểm tra 2 trang 48 Chuyên đề Tin học 12: Trong cây tìm kiếm nhị phân em vừa xây dựng ở phần vận dụng, với một số cụ thể trong dây em hãy cho biết cần bao nhiều bước so sánh để tìm ra nút có giá trị khóa đó trên cây.

Lời giải:

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.