Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

NHIỆT LIỆT

CHÀO ĐÓN CẢ LỚP ĐẾN VỚI BUỔI HỌC HÔM NAY!

a) Nếu thực hiện thuật toán duyệt giữa (trái - gốc – phải) thì nút đầu tiên được duyệt là nút nào?

b) Nút cuối cùng được duyệt là nút nào?

c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.

Quan sát cây tìm kiếm nhị phân trong Hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:

KHỞI ĐỘNG

BÀI 9:

CÁC THUẬT TOÁN DUYỆT TRÊN CÂY TÌM KIẾM NHỊ PHÂN

NỘI DUNG BÀI HỌC

1. CÁC THUẬT TOÁN DUYỆT CÂY TÌM KIẾM NHỊ PHÂN

2. SẮP XẾP DÃY SỐ BẰNG CÂY TÌM KIẾM NHỊ PHÂN

PHẦN 1.

CÁC THUẬT TOÁN DUYỆT CÂY TÌM KIẾM NHỊ PHÂN

HOẠT ĐỘNG NHÓM 4

Phân biệt sự khác nhau giữa các thuật toán duyệt cây nhị phân đã học trong Bài 6 và các thuật toán duyệt trong bài học này.

Nếu cây tìm kiểm nhị phân được biểu diễn bằng mảng T thì cần kiểm tra điều kiện gì?

Trả lời

• Trong bài 6: Mô hình cây là cây nhị phân hoàn chỉnh.
• Trong bài học này: cây tìm kiếm nhị phân đã được bổ sung thêm các phần tử giả None để trở thành cây nhị phân hoàn chỉnh.
• Trong quá trình duyệt luôn phải kiểm tra xem nút đang duyệt có phải là nút giả None hay không.

Nếu cây tìm kiếm nhị phân được biểu diễn bằng mảng T thì cần kiểm tra điều kiện k < len(T) và T[k] ≠ None để nút tại chỉ số k không là nút giả None.

a. Thuật toán duyệt trước

• Thuật toán duyệt trước bắt đầu từ nút k:
• Lệnh duyệt trước toàn bộ cây tìm kiếm nhị phân T là:

b. Thuật toán duyệt sau

• Thuật toán duyệt sau bắt đầu từ nút k:
• Lệnh duyệt sau toàn bộ cây tìm kiếm nhị phân T là:

c. Thuật toán duyệt giữa

• Thuật toán duyệt sau bắt đầu từ nút k:

Lưu ý: Thuật toán duyệt này sẽ duyệt các nút lần lượt theo thứ tự tăng dần của khoá.

Lệnh duyệt giữa và in ra màn hình toàn bộ các khoá cây tìm kiếm nhị phân T theo thứ tự tăng dần là:

d. Thuật toán duyệt ngược

• Thuật toán duyệt ngược bắt đầu từ nút k:

Lưu ý: Thuật toán duyệt này sẽ duyệt các nút lần lượt theo thứ tự giảm dần của khóa.

Lệnh duyệt ngược và in ra màn hình toàn bộ các khoá cây tìm kiếm nhị phân T theo thứ tự giảm dần là:

Câu 1. Cho dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.

Câu 2. Với cây T như Câu 1, nếu thực hiện thuật toán duyệt ngược thì thứ tự các khoá thể hiện trên màn hình như thế nào?

CỦNG CỐ

Câu 1.

Các khoá được duyệt theo thuật toán duyệt giữa là: 0, 1, 2, 5, 9.

Câu 2.

Các khoá được duyệt theo thuật toán duyệt ngược là: 9, 5, 2, 1, 0.

Trả lời câu hỏi Củng cố

KẾT LUẬN

Các thuật toán duyệt chính trên cây tìm kiếm nhị phân bao gồm duyệt trước, duyệt giữa, duyệt sau và duyệt ngược.

• Thuật toán duyệt giữa sẽ duyệt các nút của cây theo thứ tự tăng dần của khoá.
• Thuật toán duyệt ngược sẽ duyệt các nút của cây theo thứ tự giảm dần của khoá.

IDEA GENERATION

PROTOTYPING

RESEARCH

& ANALYSIS

TESTING AND REFINEMENT

FINAL PRODUCTION

PHẦN 2.

SẮP XẾP DÃY SỐ BẰNG CÂY TÌM KIẾM NHỊ PHÂN

HOẠT ĐỘNG NHÓM

Thảo luận nhóm, đưa ra ý tưởng thiết kế thuật toán sắp xếp dãy giữa trên thuật toán duyệt giữa của cây tìm kiến nhị phân.

Thuật toán sắp xếp dãy số bằng cách tìm kiếm nhị phân

Đoạn mã giả của thuật toán:

Cách xử lí các khóa trùng nhau của cây tìm kiến nhị phân

Cách 1: Bổ sung biến để lưu thông tin về số lần lặp của các khoá trên cây T. Bên cạnh mảng T, cần có thêm mảng C với ý nghĩa như sau: C[k] = số lần lặp của khoá T[k]. Mảng C có độ dài bằng T và được cập nhật đồng thời với T.

Cách 2: Định nghĩa cây tìm kiếm nhị phân cho phép các khoá trùng nhau.

Thiết lập theo cách 2

• Hàm chèn khóa v vào cây tìm kiếm nhi phân T:

Thiết lập theo cách 2

• Viết lại thuật toán duyệt giữa bằng hàm new_inorder (T, k, A). Hàm sẽ thực hiện duyệt giữa trên cây tìm kiếm nhị phân T bắt đầu từ nút k, trong khi duyệt sẽ đưa các giá trị khoá của các nút được duyệt vào mảng A.

Thiết lập theo cách 2

• Đoạn mã giả mô tả thuật toán sắp xếp dãy trên có thể được viết lại trên mô hình cây tìm kiếm nhị phân mới, sử dụng thư viện cây tìm kiếm nhị phân BST.py.

Câu 1. Viết lại hàm BSTSort(A) thực hiện sắp xếp dãy số A theo thứ tự tăng dần nhưng kết quả không cập nhật vào A. Hàm trả lại dãy số mới là dãy vừa được sắp xếp (gồm các phần tử của dãy A).

Câu 2. Nếu không cần cập nhật vào dãy A mà chỉ cần in ra màn hình các phần tử của A theo thứ tự tăng dần thì cần sửa lại chương trình sắp xếp trên như thế nào?

Câu 1

Hàm BSTSort(A) thực hiện sắp xếp dãy A nhưng không cập nhật vào A, hàm sẽ trả lại dãy mới là sắp xếp theo thứ tự tăng dần của A.

Câu 2

Sử dụng thuật toán duyệt giữa:

KẾT LUẬN

Có thể thiết lập thuật toán sắp xếp danh sách theo kĩ thuật sử dụng cây tìm kiếm nhị phân bằng cách duyệt giữa trên cây tìm kiếm nhị phân được tạo bởi danh sách.

LUYỆN TẬP

(trả lời câu hỏi trắc nghiệm)

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Cho trước dãy số B =[3,2,10,1,3,2,7]. Thực hiện thuật toán duyệt giữa trên cây tìm kiếm nhị phân. Kết quả duyệt là dãy các khoá có thứ tự:

A. 1, 2, 3, 7, 10

B. 1, 3, 10, 7, 2

C. 10, 7, 3, 2, 1

D. 7, 10, 3, 2, 1

A. 1, 2, 3, 7, 10

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 2. Kết quả của việc duyệt giữa trên một cây tìm kiếm nhị phân sẽ tạo ra:

--------------- Còn tiếp ---------------