Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 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 gọi hai HS lên tham gia trò chơi ở Hoạt động 1:

An và Hoà 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ị khoá từng nút của cây này, từ đó đưa ra một cách giúp Hoà đặt ít câu hỏi nhất có thể để tìm ra vị trí nút có giá trị khoá 55.

Hình 2. Ví dụ cây tìm kiếm nhị phân

Cách tham gia:

• Một bạn ghi nhớ cấu trúc cây nhị phân biểu diễn dãy số: 45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58.

• Bạn còn lại sẽ đặt các câu hỏi để tìm ra nút có giá trị khoá bằng 55 trên cây nhị phân.

- GV đưa ra cách hỏi tối ưu, tổng kết lại và đưa ra định nghĩa cây tìm kiếm nhị phân.

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

- HS tham gia trò chơi ở Hoạt động 1 theo hướng dẫn của GV.

- GV quan sát và trợ giúp 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 đưa ra cách tìm ra vị trí nút có giá trị khoá cho trước trên cây nhị phân.

- 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

- GV nhận xét, góp ý cho câu trả lời của HS.

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

- GV chuyển sang nội dung tiếp theo.

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

- Quan sát cây nhị phân ở Hình 2, ta có nhận xét: Giá trị khoá mỗi nút trong lớn hơn giá trị khoá của các nút thuộc cây con trái của nó (nếu có) và bé hơn giá trị khoá của các nút thuộc cây con phải của nó (nếu có). 

Hoà chỉ cần đặt bốn câu hỏi là xác định được vị trí nút có giá trị khoá 55:

Câu hỏi 1: “Nút thứ 0 có giá trị khoá bằng, nhỏ hơn hay lớn hơn 55?”. 

Trả lời: “45 nhỏ hơn 55”  55 chắc chắn sẽ nằm trong cây con phải của nút thứ 0.

Câu hỏi 2: “Nút thứ 2 có giá trị khoá bằng, nhỏ hơn hay lớn hơn 55?”. 

Trả lời: “60 lớn hơn 55”  55 chắc chắn sẽ nằm trong cây con trái của nút thứ 2.

Câu hỏi 3: “Nút thứ 4 có giá trị khoá bằng, nhỏ hơn hay lớn hơn 55?”. “

Trả lời: “46 nhỏ hơn 55”  55 chắc chắn sẽ nằm trong cây con phải của nút thứ 4.

Câu hỏi 4: “Nút thứ 7 có giá trị khoá bằng, nhỏ hơn hay lớn hơn 55?”. 

Trả lời: “55 bằng 55”  55 là nút thứ 7.

Nhận xét:

+ Nếu hỏi ở tất cả các nút thì số lượng câu hỏi có thể lên đến bằng với số lượng phần tử của dãy số.

+ Áp dụng ý tưởng: 

• Bắt đầu hỏi từ nút gốc, mỗi lần hỏi giá trị khoá tại nút hiện hành có bằng, lớn hơn hay nhỏ hơn 55. 

• Câu trả lời sẽ giúp người hỏi xác định được nút cần tìm hoặc bỏ qua cây con bên trái hoặc bỏ qua cây con bên phải. 

• Nếu chưa phải nút cần tìm, người hỏi tiếp tục với nút gốc của cây con phía không bị bỏ qua.

Phương pháp này chỉ áp dụng được trên cây có cấu trúc là cây tìm kiếm nhị phân.

Cây nhị phân ở Hình 2 là cây tìm kiếm nhị phân. 

Khái niệm: Cây tìm kiếm nhị phân gồm các nút có giá trị khoá đôi một khác nhau có thể được định nghĩa đệ quy như sau:

1. Cây rỗng là một cây tìm kiếm nhị phân.

2. Mọi nút thuộc cây con trái của nút gốc có khoá nhỏ hơn khóa nút gốc. 

3. Mọi nút thuộc cây con phải của nút gốc có khoá lớn hơn khoá nút gốc.

4. Cả cây con trái và cây con phải của nút gốc cũng là 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

- Xuất phát từ một dãy số A, GV mô phỏng chi tiết từng bước quá trình xây dựng cây tìm kiếm nhị phân bằng cách chèn từng phần tử có khoá là giá trị từng phần tử của A vào cây, bắt đầu từ cây rỗng. 

- GV phân tích ví dụ minh hoạ để HS hiểu rõ về quá trình bổ sung nút vào cây.

- GV lưu ý HS về cách chọn thứ tự lấy các phần tử trong mảng để chèn vào cây tìm kiếm nhị phân.

- GV yêu cầu HS làm việc độc lập, viết mã giả mô tả thuật toán chèn:

Em hãy viết mã giả mô tả thuật toán chèn một nút có khoá x vào cây tìm kiếm nhị phân.

- GV yêu cầu HS thực hiện phần Thực hành SGK tr.45.

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

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

- GV quan sát và trợ giúp 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 lần lượt thực hiện các nhiệm vụ học tập.

- GV mời 1 – 2 HS trình bày kết quả Thực hành.

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

- Từ kết quả thực hành của HS, 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 chuyển sang nội dung tiếp theo.

2. Xây dựng cây tìm kiếm nhị phân

- Với một dãy A gồm n số nguyên dương, cây tìm kiếm nhị phân được xây dựng từ dãy A bằng cách chèn từng nút có khoá là giá trị từng phần tử của A vào cây bắt đầu từ cây rỗng.

- Thuật toán đệ quy chèn một nút có khoá x vào cây tìm kiếm nhị phân như sau:

• Nếu cây rỗng, tạo nút mới là nút gốc của cây có khoá là x. Kết thúc quá trình chèn. Nút mới chèn luôn là nút lá.

• Trái lại, gọi khoá nút gốc là khoa_nut_goc:

• Nếu x < khoa_nut_goc, chèn x sang cây con trái của nút gốc.

• Nếu x > khoa_nut_goc, chèn x sang cây con phải của nút gốc.

Thực hiện lặp lại n lần thuật toán trên, mỗi lần với một phần tử dãy A lần lượt bắt đầu từ phần tử thứ nhất sẽ nhận được một cây tìm kiếm nhị phân.

Ví dụ: Hình 3 mô tả các bước chèn nút mới có giá trị khoá 33 vào cây tìm kiếm nhị phân đang biểu diễn tập 5 số nguyên dương 26, 21, 36, 12, 40.

Hình 3. Minh hoạ chèn nút mới 
có giá trị khóa 33 vào cây

Lưu ý: 

• Có thể chọn bất kì thứ tự lấy các phần tử trong mảng A để chèn vào cây tìm kiếm nhị phân. Vì vậy các cách chọn thứ tự lấy phần tử trong mảng để chèn có thể tạo thành nhiều cây tìm kiếm nhị phân khác nhau. 

• Thông thường, để dễ kiểm soát, người ta hay chọn lần lượt theo thứ tự phần từ từ đầu màng đến cuối mảng, mỗi phần tử lấy đúng một lần.

- Mã giả mô tả thuật toán chèn một nút có khóa x vào cây tìm kiếm nhị phân là cây nut_goc. Nếu cây nut_goc khác rỗng thì nút gốc của cây này là nut_goc.

Hình 4. Mã giả mô tả thuật toán chèn

Thực hành: 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ị khoá 33, em hãy mô tả từng bước chèn một nút mới có giá trị khoá bằng 28 vào cây.

• So sánh 28 và 26, duyệt cây con phải.

• So sánh 28 và 36, duyệt tiếp cây con trái.

• So sánh 28 và 33, duyệt tiếp cây con trái.

• Chèn 28 như là nút con trá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 yêu cầu HS suy nghĩ và trả lời câu hỏi:

Theo em, có thể xảy ra những trường hợp nào khi tìm kiếm một nút trên cây tìm kiếm nhị phân?

- Từ đó, GV trình bày thuật toán đệ quy tìm kiếm nút trên cây tìm kiếm nhị phân.

- GV mô phỏng chi tiết từng bước quá trình tìm kiếm một nút có giá trị cho trước trên cây tìm kiếm nhị phân ở Hình 5 SGK tr.46.

- GV lưu ý HS về thứ tự chèn các phần tử vào cây tìm kiếm nhị phân.

- GV yêu cầu HS viết mã giả mô tả thuật toán tìm kiếm:.

3. Tìm kiếm nút trên cây tìm kiếm nhị phân

- Thuật toán đệ quy tìm kiếm một nút có khoá x trên cây tìm kiếm nhị phân:

• Nếu cây rỗng, kết thúc quá trình tìm kiếm, cây không chứa nút có khoá x cần tìm.

• Trái lại:

• Nếu x = khoa_nut_goc, nút gốc hiện tại là nút có khoá x cần tìm trong cây ban đầu. Kết thúc quá trình tìm kiếm.

• Nếu x < khoa_nut_goc, tìm kiếm x sang cây con trái của nút gốc.

• Nếu x > khoa_nut_goc, tìm kiếm x sang cây con phải của nút gốc.

Sau mỗi bước so sánh, quá trình tìm kiếm xét đến độ sâu tăng thêm 1. Do đó, số bước so sánh để tìm kiếm một nút trên cây tìm kiếm nhị phân không vượt quá chiều cao của cây cộng 1.