Giáo án NLS chuyên đề Tin học 12 KHMT Bài 7: Cây tìm kiếm nhị phân

Ngày soạn: …/…/…

Ngày dạy: …/…/…

BÀI 7: CÂY TÌM KIẾM NHỊ PHÂN

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

• Nêu được khái niệm cây tìm kiếm nhị phân.
• Trình bày các thuật toán tạo cây tìm kiếm nhị phân, chèn thêm nút vào cây tìm kiếm nhị phân.
• Trình bày thuật toán tìm kiếm khoá trên cây tìm kiếm nhị phân.

2. Năng lực

Năng lực chung: 

• Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.
• Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.
• Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

• Trình bày được khái niệm cây tìm kiếm nhị phân.
• Mô phỏng được thuật toán tạo cây tìm kiếm nhị phân từ một tập hợp các số cho trước.
• Biết và thực hiện được thuật toán tìm kiếm một giá trị của cây tìm kiếm nhị phân.

Năng lực số:

• 3.4.NC1a: Lập trình (HS viết, đọc và điều chỉnh các hàm Python thực hiện thao tác chèn, tìm kiếm và kiểm tra biểu diễn trên cây tìm kiếm nhị phân).
• 2.1.NC1a: Tương tác thông qua công nghệ số (HS xem video được tạo bởi công cụ AI và trả lời câu hỏi, sử dụng máy tính cá nhân hoặc thiết bị di động có kết nối Internet để làm bài tập trắc nghiệm củng cố trên môi trường số).
• 5.3.NC1a: Sử dụng sáng tạo công nghệ số (HS sử dụng môi trường lập trình Python để mô phỏng, thực thi và kiểm thử thuật toán chèn/tìm kiếm).
• 5.2.NC1b: Xác định nhu cầu và giải pháp công nghệ (HS sử dụng công cụ tìm kiếm và trợ lý AI để giải quyết nhu cầu tra cứu, mở rộng tri thức).
• 1.3.NC1a: Quản lí dữ liệu, thông tin và nội dung số (HS thực hiện thao tác vẽ sơ đồ mảng biểu diễn cây hoặc gõ mã mô tả trên máy tính để tổ chức, biểu diễn và truy xuất dữ liệu của cây tìm kiếm nhị phân bằng mảng một chiều).
• 1.2.NC1a: Đánh giá dữ liệu, thông tin và nội dung số (HS thực hiện phân tích đối chiếu kết quả gợi ý từ công cụ số/AI với SGK, thuật toán gốc và kết quả tự làm của bản thân để khẳng định tính chính xác của dữ liệu).
• 6.2.NC1a: Sử dụng trí tuệ nhân tạo (HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản).
• 1.1.NC1a: Duyệt, tìm kiếm và lọc dữ liệu, thông tin và nội dung số (HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV).
• 1.1.NC1b: Duyệt, tìm kiếm và lọc dữ liệu, thông tin và nội dung số (Áp dụng được kỹ thuật tìm kiếm để lấy được dữ liệu, thông tin và nội dung trong môi trường số).

Năng lực AI:

• 12.A3.1: Trách nhiệm công dân trong xã hội có AI (HS sử dụng AI an toàn, trung thực, tự tư duy thuật toán trước, không sao chép nguyên văn lời giải/mã chương trình của AI; thực hiện kiểm chứng chéo kết quả và cam kết không lạm dụng, phụ thuộc hoàn toàn vào AI để giải hộ bài).
• 12.C2.1: Các yêu cầu dành cho công cụ AI hỗ trợ các hoạt động học tập và xã hội (HS biết cách thiết lập câu lệnh (prompt) phù hợp để nhờ Chatbot AI giải thích tri thức lập trình, so sánh hiệu năng các thuật toán hoặc phân tích trường hợp suy biến của cây tìm kiếm nhị phân).

3. Phẩm chất

• Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.
• Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.
• Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

• SGK, KHBD Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
• Phòng thực hành máy tính cài đặt sẵn môi trường lập trình Python (IDLE, PyCharm, VS Code,…) và có kết nối Internet, máy trình chiếu.
• Học liệu số & Công cụ AI:
• Phiếu bài tập số/bộ câu hỏi trắc nghiệm trên phần mềm Quizizz/website kenhhoctap.edu.vn.
• Video AI được tạo bằng các công cụ AI để khởi động bài học.
• Công cụ Chatbot AI (ChatGPT/Gemini).

2. Đối với học sinh

• SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
• Vở ghi. 

III. TIẾN TRÌNH DẠY HỌC

1. HOẠT ĐỘNG KHỞI ĐỘNG

…………………………………………..

…………………………………………..

…………………………………………..

2. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu cấu trúc cây tìm kiếm nhị phân

a. Mục tiêu: HS biết được định nghĩa chính xác của cây tìm kiếm nhị phân và biết được một số cách biểu diễn cây tìm kiếm nhị phân trên máy tính.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành được kiến thức bài học. HS nhận biết cây tìm kiếm nhị phân.

d. Tổ chức thực hiện:

Hoạt động 2. Thuật toán chèn khóa mới vào cây tìm kiếm nhị phân

a. Mục tiêu: HS hiểu được thuật toán chèn một nút có khoá mới vào một cây tìm kiếm nhị phân T cho trước, sao cho sau khi chèn cây T vẫn là cây tìm kiếm nhị phân.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành kiến thức bài học. HS biểu diễn cây nhị phân bằng mảng một chiều.

d. Tổ chức thực hiện:

…………………………………………..

…………………………………………..

…………………………………………..

Hoạt động 3: Tìm hiểu thuật toán tìm kiếm trên cây tìm kiếm nhị phân

a. Mục tiêu: HS hiểu được thuật toán tìm kiếm khoá trên cây tìm kiếm nhị phân, hiểu được tính ưu việt của việc tìm kiếm trên cây tìm kiếm nhị phân.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 3, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành kiến thức bài học. HS hiểu được thuật toán tìm kiếm khoá trên cây tìm kiếm nhị phân.

d. Tổ chức thực hiện:

3. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Giúp HS hệ thống lại kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phiếu bài tập.

c. Sản phẩm học tập: Phiếu bài tập.

d. Tổ chức thực hiện:

…………………………………………..

…………………………………………..

…………………………………………..

4. HOẠT ĐỘNG VẬN DỤNG

a. Mục tiêu: HS vận dụng được kiến thức của bài học để trả lời câu hỏi, thực hành hoàn thành nhiệm vụ được giao.

b. Nội dung: HS vận dụng các kiến thức đã học, thảo luận trả lời theo yêu cầu của GV.

c. Sản phẩm học tập: HS hoàn thành tìm hiểu kiến thức.

d. Tổ chức thực hiện:

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

- GV yêu cầu HS hoạt động nhóm đôi hoàn thành bài tập phần Vận dụng SGK tr.29.

Câu 1. Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn. Danh sách được cho trong tệp văn bản có dạng như bảng bên.

Viết chương trình đọc tệp dữ liệu đầu vào trên và liên tục thực hiện các thao tác sau:

a) Nhập thêm vào danh sách học sinh và điểm trung bình.

b) Tìm kiếm với yêu cầu nhập họ tên học sinh và đưa ra kết quả họ tên học sinh, điểm trung bình hoặc thông báo "không tìm thấy".

Chương trình kết thúc khi nhập vào một xâu rỗng. Yêu cầu giải bài này bằng cây o một xâu rồng tìm kiếm nhị phân.

Câu 2. 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.

Câu 3. Cho trước dãy A bao gồm các số nguyên và các giá trị None. Viết chương trình kiểm tra xem A 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?

Vi du:

Dãy [10, 7, 0, 5, None, 3] là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi. 

Dãy [1, 6, None, 2, 3, None, 4] không là biểu diễn của cây nhị phân tổng quát nào.

Câu 4. Cho trước dãy A bao gồm các số nguyên và các giá trị None. Viết chương trình kiểm tra xem A có phải là biểu diễn của một cây tìm kiếm nhị phân hay không.

Ví dụ:

Dãy [5, 3, 6, None, 4, None, 10] là biểu diễn của cây tìm kiếm nhị phân.

Dãy [2, 1, 5, None, 3, 4, 10] không là biểu diễn của cây tìm kiếm nhị phân (mặc dù dãy này là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi).

- GV định hướng khai thác AI có trách nhiệm (Khi nào nên/không nên dùng AI): 

+ Các nhóm tư duy, thảo luận giải pháp thuật toán ra giấy trước và tự lập trình mã nguồn Python. 

+ Sau khi tự gõ xong bản nháp code, các nhóm được phép sử dụng Chatbot AI làm trợ lý để tối ưu hóa code và gỡ lỗi biên dịch.

- GV quán triệt: "AI là người bạn đồng hành đắc lực để gợi ý ý tưởng thuật toán, gỡ lỗi và phân tích nhưng các em tuyệt đối không được chép nguyên văn code do AI giải hộ để nộp bài đối phó. Hãy thể hiện tinh thần liêm chính khoa học trong thời đại số".

- GV đặt câu hỏi mở rộng: "Hãy giải thích tại sao một mảng hoàn chỉnh [2, 1, 5, None, 3, 4, 10] tuy có các con trực tiếp thỏa mãn con trái nhỏ hơn cha và con phải lớn hơn cha (1 < 2 < 5; 3 < 5 < 10) nhưng lại không phải là cây BST?" 

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

- HS tiếp nhận, thực hiện nhiệm vụ, thảo luận, đưa ra câu trả lời.

- GV quan sát quá trình HS thảo luận, hỗ trợ khi HS cần.

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

- GV cho HS trả lời.

Gợi ý đáp án:

Câu 1. 

…………………………………………..

…………………………………………..

…………………………………………..

Câu hỏi mở rộng: Do nút 4 nằm ở cây con trái của nút gốc 5 nhưng có giá trị 4 < 5. Theo quy tắc BST, mọi nút ở cây con trái của 5 bắt buộc phải nhỏ hơn 5, nhưng nút 4 là con phải của nút 3 thì lại thỏa mãn 4 > 3. Tính chất BST bị vi phạm ở mối quan hệ xuyên thế hệ. Thuật toán của ta ở Câu 4 sử dụng leftmost/rightmost đã phát hiện và bắt lỗi chính xác trường hợp này.

- HS khác quan sát, lắng nghe, nhận xét và bổ sung.

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

- GV chính xác hoá lại các nội dung trả lời của HS.

- GV chuẩn kiến thức và kết thúc tiết học.

[3.4.NC1a: HS viết, đọc và điều chỉnh các hàm Python giải quyết bài toán quản lý danh sách học sinh và kiểm tra biểu diễn cây nhị phân/BST hoàn chỉnh.

5.3.NC1a: HS áp dụng công cụ lập trình Python IDE thiết kế, thực thi thành công chương trình kiểm thử các bài toán vận dụng trên môi trường lập trình.

12.A3.1: HS thể hiện trách nhiệm học thuật số thông qua việc tự lập trình thuật toán trước, sử dụng AI có kiểm soát để debug mã nguồn, rà soát tính chuẩn xác và cam kết không phụ thuộc hoàn toàn vào công cụ công nghệ.

12.C2.1: HS đặt câu lệnh (prompt) phù hợp cho Chatbot AI để tra cứu thông tin chuyên sâu giải thích bản chất lỗi logic biên của cây BST.]

* HƯỚNG DẪN VỀ NHÀ

- Xem lại kiến thức đã học ở Bài 7.

- Xem trước nội dung Bài 8: Thực hành cây tìm kiếm nhị phân