Giáo án chuyên đề Khoa học máy tính 12 chân trời Bài 2.3: Cây tìm kiếm nhị phân

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS hoạt động cá nhân, quan sát Hình 1 và thực hiện yêu cầu:

+ Em hãy chỉ ra và cho biết vị trí các nút có giá trị nhỏ hơn 20 và các nút có giá trị lớn 40 nằm ở đâu trên cây nhị phân?

- Từ đó, GV tổng quát hoá và giới thiệu cho HS về khái niệm cây tìm kiếm nhị phân.

- GV hướng dẫn HS tìm hiểu về cách đánh chỉ số cho các nút trên cây tìm kiếm nhị phân bằng cách trả lời câu hỏi:

+ Em hãy quan sát Hình 2 và trình bày:

• Cách đánh chỉ số cho các nút trên cây tìm kiếm nhị phân.

• Cách lưu trữ cây tìm kiếm nhị phân vào mảng một chiều.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm SGK tr.41:

Hình nào trong Hình 3 biểu diễn cây tìm kiếm nhị phân?

Hình 3a.

Hình 3b.

Hình 3. Các cây nhị phân

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung SGK và thực hiện các yêu cầu mà GV đưa ra.

- GV quan sát, hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS trả lời các câu hỏi và nhận xét lẫn nhau. 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.41:

+ Hình 3a là cây tìm kiếm nhị phân.  

+ Hình 3b không phải cây tìm kiếm nhị phân vì nút 3 có giá trị lớn hơn nút 2 (nút 2 thuộc 1 cây con bên phải nút 3).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nêu nhận xét, chính xác hoá lại các nội dung trả lời của HS.

- GV chốt kiến thức như nội dung ở hoạt động Ghi nhớ: 

1. Khái niệm cây tìm kiếm nhị phân

- Trong cây nhị phân ở Hình 1, giá trị của nút bất kì luôn lớn hơn giá trị của tất cả nút thuộc cây con trái và nhỏ hơn giá trị của tất cả nút thuộc cây con phải. 

Cây nhị phân thoả tính chất này được gọi là cây tìm kiếm nhị phân.

- Cách đánh chỉ số cho các nút trên cây tìm kiếm nhị phân:

+ Nút gốc có chỉ số 0.

+ Nút có chỉ số i:

• Nút con trái có chỉ số 2*i + 1.

• Nút con phải có chỉ số 2*i + 2.

Hình 2. Cây tìm kiếm nhị phân sau khi được đánh chỉ số cho các nút

- Cách lưu trữ cây tìm kiếm nhị phân vào mảng một chiều T: Giá trị của nút có chỉ số i được lưu trữ vào phần tử T[i].

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV cho HS xác định được từ một tập hợp các số nguyên dương có thể biểu diễn thành nhiều cây tìm kiếm nhị phân.

- GV chia lớp thành các nhóm 3 – 4 HS, yêu cầu HS thảo luận và thực hiện các yêu cầu:

+ Hãy dùng mảng một chiều để biểu diễn các giá trị trên cây tìm kiếm nhị phân ở Hình 4b.

+ Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên cây tìm kiếm nhị phân ở Hình 4b.

- Sau đó, GV yêu cầu các nhóm đưa ra nhận xét:

+ Phép toán duyệt cây nhị phân nào cho kết quả là một dãy các giá trị tăng dần?

- GV hỗ trợ HS thực hiện mô phỏng thuật toán xây dựng cây tìm kiếm nhị phân từ tập hợp số nguyên dương cho trước.

- GV hướng dẫn, gợi ý HS đọc nội dung trong SGK kết hợp thực hiện “chạy” thuật toán bằng tay từng bước trên giấy nháp hoặc vở.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm tr.44 SGK: 

Cho mảng A = [5, 7, 30, 23, 34, 15] Hãy vẽ cây tìm kiếm nhị phân biểu diễn mảng A.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung SGK sau đó trao đổi, thảo luận trả lời các câu hỏi mà GV đưa ra.

- GV quan sát, hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm báo cáo kết quả thảo luận.

- GV mời HS khác nhận xét, bổ sung. 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.44:

Cây nhị phân biểu diễn mảng A:

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả thảo luận của các nhóm, chính xác hoá lại các nội dung trả lời của HS.

- GV chốt kiến thức như nội dung ở hoạt động Ghi nhớ: 

2. Mô phỏng thuật toán tạo cây tìm kiếm nhị phân

a) Cây tìm kiếm nhị phân biểu diễn một tập số nguyên dương

- Từ một tập hợp các số nguyên dương có thể biểu diễn thành nhiều cây tìm kiếm nhị phân.

Ví dụ: Cây tìm kiếm nhị phân ở Hình 4a và Hình 4b biểu diễn cùng một tập hợp A ở hoạt động KHỞI ĐỘNG, nhưng có chiều cao khác nhau.

Hình 4a.

Hình 4b.

Hình 4. Hai cây tìm kiếm nhị phân biểu diễn cùng một tập hợp số nguyên dương

- Duyệt cây tìm kiếm nhị phân ở Hình 4b:

• Mảng một chiều biểu diễn các giá trị trên cây: A = [30, 20, 40, 10, 24, 34, 46, 6, 14, 22, 26, 32, 37, 44, 48].

• Kết quả duyệt trước: 30, 20, 10, 6, 14, 24, 22, 26, 40, 34, 32, 37, 46, 44, 48.

• Kết quả duyệt giữa: 6, 10, 14, 20, 22, 24, 26, 30, 32, 34, 37, 40, 44, 46, 48.

• Kết quả duyệt sau: 6, 14, 10, 22, 26, 24, 20, 32, 37, 34, 44, 48, 46, 40, 30.

Phép toán duyệt giữa cây tìm kiếm nhị phân cho kết quả là một dãy các giá trị tăng dần.

b) Thuật toán tạo cây tìm kiếm nhị phân biểu diễn tập hợp số nguyên dương

Ví dụ: Xây dựng cây tìm kiếm nhị phân từ mảng A gồm các số nguyên dương: A = [15, 3, 16, 7].

Ban đầu, cây tìm kiếm nhị phân T là rỗng.

• Thêm vào khoá 15: Vì cây T rỗng Tạo nút mới có khoá 15 và cây T có nút 15.

Hình 5. Cây T có nút 15

• Thêm vào khoá 3: 

• Vì 3 < 15 Thêm 3 vào cây con trái của nút 15. 

• Nút 15 không có cây con trái Tạo nút mới có khoá 3 và nút này là nút con trái của nút 15.

Hình 6. Thêm nút mới có khoá 3 vào cây T

• Thêm vào khoá 16: 

• Vì 16 > 15 Thêm 16 vào cây con phải của nút 15. 

• Nút 15 không có cây con phải Tạo nút mới có khoá 16 và nút này là nút con phải của nút 15.

Hình 7. Thêm nút mới có khoá 16 vào cây T

• Thêm vào khoá 7: 

• Vì 7 < 15 Thêm 7 vào cây con trái của nút 15 (có gốc là nút 3). 

• Vì 7 > 3 Thêm 7 vào cây con phải của nút 3. 

• Nút 3 không có cây con phải Tạo nút mới có khoá 7 và nút này là nút con phải của nút 3.

Hình 8. Thêm nút mới có khoá 7 vào cây T

Nhận xét: Nút mới thêm vào cây tìm kiếm nhị phân luôn luôn là nút lá.

* Thuật toán sau đây tạo cây tìm kiếm nhị phân T từ một dãy số nguyên dương a. Cây T là cây nhị phân hoàn chỉnh (có thể có các nút None) được cài đặt bằng danh sách (kiểu list của Python).