Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 7: 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 thảo luận, tìm hiểu nội dung mục 1 và trả lời một số câu hỏi:

+ Nêu khái niệm cây tìm kiếm nhị phân.

+ Có thể biểu diễn dữ liệu cây nhị phân theo những cách nào? Trình bày cách biểu diễn.

+ Thế nào là cây tìm kiếm nhị phân? 

- GV giới thiệu về cây cân bằng, cây suy biến.

- 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 Củng cố tr.32 SGK:

Câu 1. Trong Hình 7.5, em hãy cho biết cây nào là cây tìm kiếm nhị phân.

Câu 2. Từ các khóa 1, 2, 3 có thể tạo ra được bao nhiêu cây tìm kiếm nhị phân? Hãy vẽ sơ đồ mô tả các cây này.

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. 

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

- Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV kết luận: 

Cây nhị phân tổng quát có thể được cài đặt bằng cấu trúc nút liên kết hoặc bằng mảng một chiều. Cây tìm kiếm nhị phân là cây nhị phân mà tại mọi nút, khoá của nút này lớn hơn khoá của các nút con thuộc cây con trái và nhỏ hơn khoá của các nút con thuộc cây con phải. Khoá của các nút là duy nhất, nghĩa là hai nút khác nhau có khoá khác nhau.

1. Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân (BST – Binary Search Tree) là một dạng đặc biệt của cây nhị phân thông thường, được tạo ra với mục đích hỗ trợ thuận tiện cho các bài toán tìm kiếm, chèn, xoá, sắp xếp.

a) Mô hình dữ liệu cây nhị phân

Có hai cách biểu diễn cây nhị phân tổng quát: 

- Cách 1: Sử dụng cấu trúc nút liên kết. Cách biểu diễn này sẽ cần hai cấu trúc:

+ Cấu trúc Node để thể hiện thông tin từng nút (node) của cây nhị phân. 

+ Cấu trúc Tree chỉ có thuộc tính root sẽ chỉ vào nút gốc của cây nhị phân.

- Cách 2: Sử dụng mảng một chiều.

Với cách này, cây nhị phân tổng quát cần được bổ sung thêm các nút giả (có giá trị None) để tạo thành cây nhị phân hoàn chỉnh đã biến đổi, sau đó sử dụng cách biểu diễn cây hoàn chỉnh này để biểu diễn.

+ Ví dụ: Cho mảng T = [5, 3, 7, 6].

Cây nhị phân tổng quát ở Hình 7.3c được thêm vào các nút giả None để trở thành cây nhị phân hoàn chỉnh và được cài đặt bằng mảng T = [5, 3, 7, None, None, 6].

- Để thiết lập nhị phân rỗng, sử dụng hàm:

b) Cây tìm kiếm nhị phân

- Cây tìm kiếm nhị phân là cây nhị phân, có hai tính chất quan trọng:

• Khoá của mỗi nút của cây lớn hơn khoá của tất cả các nút thuộc cây con trái và nhỏ hơn khoá của tất cả các nút thuộc cây con phải của nó.

• Hai nút khác nhau có khoá khác nhau.

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

+ Cây cân bằng: cây tìm kiếm nhị phân mà tại mọi nút thì chiều cao của cây con trái và của cây con phải lệch nhau nhiều nhất là 1. (Hình 7.4a).

Thuật toán tìm kiếm nhị phân.

+ Cây suy biến: cây tìm kiếm nhị phân có chiều cao lớn nhất, mỗi nút chỉ có tối đa một nút con. (Hình 7.4b)

Thuật toán tìm kiếm tuần tự.

- Khi cây tìm kiếm nhị phân được cài đặt bằng mảng T, tại mọi nút k, với mọi nút i thuộc cây con trái và với mọi nút j thuộc cây con phải, ta có bất đẳng thức:

T[i] < T[k] < T[j]

Lưu ý: Nếu cây nhị phân T là cây tìm kiếm nhị phân thì mọi cây con của T cũng là cây tìm kiếm nhị phân.

Hướng dẫn trả lời câu hỏi Củng cố tr.32 SGK:

Câu 1. Trường hợp b)

Câu 2. 

Có 5 cách thiết lập cây tìm kiếm nhị phân từ các khóa 1, 2, 3.

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 nêu Bài toán:

Bài toán: Cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân. Quan sát, thảo luận, tìm hiểu thuật toán tìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.

- GV hướng dẫn HS thực hiện, sau đó gọi nhóm HS lên trình bày lại (có thể sử dụng nút khóa khác nhau).

- GV yêu cầu:

Nêu các bước chính để chèn một khóa v vào cây tìm kiếm nhị phân T.

- HS tìm hiểu SGK, GV giới thiệu đoạn chương trình mô tả thao tác chèn một khóa vào cây tìm kiếm nhị phân.

+ Bước 1 thực hiện tim vị trí cần chèn khoá v bắt đầu từ nút gốc T[0] cho đến khi gặp nút giả T[k] = None hoặc tìm thấy nút T[k] = v thì kết thúc. 

+ Bước 2 thực hiện chèn khoá v vào cây T tại nút k. Nếu k  len(T) thì ta phải thêm các nút giá None từ chỉ số len(T) đến chỉ số k để cây T là cây nhị phân hoàn chỉnh. Số nút giả None phải thêm vào là k - len(T) + 1.

- 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 Củng cố tr.34 SGK:

Câu 1. Cho trước dây các số A = [10,1,2,11,8,15,20,9,0]. Hãy mô tả và vẽ sơ đồ cây nhị phân biểu diễn dãy số trên sau khi thực hiện thao tác chèn như đã mô tả trong hoạt động.

Câu 2. Với cây nhị phân đã có ở Câu 1, em hãy vẽ sơ đồ cây sau khi chèn khoá 14 và cho biết vị trí của khoá này ở trong cây.

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. 

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

- Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV kết luận: 

+ Quá trình chèn một khoá v vào cây tìm kiếm nhị phân T gồm hai bước:

Bước 1. Tìm vị trí chính xác cần chèn. Nếu gặp khoá v thì dùng chương trình. 

Bước 2. Thực hiện thao tác chèn.

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

Hướng dẫn thực hiện

- Thiết lập cấu trúc nút mới với khoá 7 sẵn sàng chèn vào cây tìm kiếm nhị phân T.

- Bước 1: Tìm vị trí cần chèn khoá v trên cây T (Hình 7.6b).

+ Bắt đầu từ nút gốc.

+ Vì nút gốc có khoá 5 < 7, nên sẽ chuyển tìm tiếp sang nút con phải của nút gốc (với khoá 10).

+ Nút hiện thời có khoá 10 > 7 nên sẽ chuyển tìm tiếp sang nút con trái của nút hiện thời (với khoá 8).

+ Nút hiện thời là 8 > 7 nên sẽ chuyển tìm tiếp sang nút con trái của nút hiện thời. Nhưng nút con trái này là None, do vậy đây chính là vị trí cần chèn nút mới.

- Bước 2: Chèn khoá v vào cây T (Hình 7.6c).

+ Chèn nút mới với khoá 7 vào vị trí là nút con trái của nút với khoá 8. 

+ Trong trường hợp khoá v không có trong cây T thì chèn khoá v vào cây này bằng cách tạo nút thật mới tại nút giả None và gán khoá v cho nút mới này.

Kết luận:

Quá trình chèn một khoá v vào cây tìm kiếm nhị phân T gồm hai bước:

Bước 1. Tìm vị trí chính xác cần chèn. Nếu gặp khoá v thì dứng chương trình. 

Bước 2. Thực hiện thao tác chèn.

*) Đoạn chương trình:

Hàm Tree_Insert(T, v) dùng để chèn khoá v vào cây tìm kiếm nhị phân T được cài đặt bằng một danh sách (thuộc kiểu list của Python).

Đoạn chương trình sau thực hiện việc tạo cây tìm kiếm nhị phân từ một tập hợp các phần tử cho trước.

Hướng dẫn trả lời câu hỏi Củng cố

Câu 1: Kết quả cây tìm kiếm nhị phân

Câu 2: Sơ đồ cây sau khi chèn khóa 14:

Chèn khoá 14 vào vị trí là nút con trái của nút với khoá 15.

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 quan sát quá trình tìm kiếm khoá trên cây tìm kiếm nhị phân thông qua các ví dụ cụ thể trong Hoạt động 3:

a) Tìm kiếm khoá 18. Trình tự tìm kiếm: 11 20 15 16 None (không tìm thấy).

b) Tìm kiếm khoá 7. Trình tự tìm kiếm: 11 4 7 (tìm thấy)

- HS hoạt động nhóm: đề xuất thuật toán, chương trình để tìm kiếm khóa trên cây tìm kiếm nhị phân.

…………………….

3. Thuật toán tìm kiếm trên cây tìm kiếm nhị phân

*) Thuật toán: tìm kiếm một nút với khóa v 

- Bắt đầu từ nút có chỉ số k trên cây tìm kiếm nhị phân T. Nếu tìm thấy thì hàm trả về chỉ số của nút có giá trị v, ngược lại trả về -1.

- Việc tìm kiếm được thực hiện như sau:

+ Nếu k nằm ngoài khoảng chỉ số của T hoặc T[k] = None thì trả về -1.

+ Nếu T[k] = v thì dừng tìm kiếm và trả về k.

+ Nếu T[k]  v thì sẽ tìm tiếp trong cây con trái nếu v < T[k], ngược lại tìm tiếp trong cây con phải nếu T[k] < v.

*) Chương trình tìm kiếm một nút với khóa v - Cách 1: Sử dụng kĩ thuật đệ quy 

Hàm tìm kiếm sử dụng đệ quy:

- Cách 2: Không sử dụng kĩ thuật đệ quy. 

Hàm tìm kiếm không sử dụng đệ quy:

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