Giáo án điện tử 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

VUI MỪNG CHÀO ĐÓN CÁC EM ĐẾN BÀI HỌC MỚI!

KHỞI ĐỘNG

Cho tập hợp A gồm các số nguyên dương A = {6, 14, 10, 34, 40, 30, 46, 20, 24, 22} được lưu trữ bằng hai cách sau:

Cách 1: Lưu vào mảng một chiều.

Cách 2: Lưu vào các nút của cây nhị phân.

Cho giá trị x = 20. Em hãy trình bày:

a) Cách tìm kiếm x trong mảng A.

b) Cách tìm kiếm x trong cây nhị phân.

Gợi ý trả lời:

a) Bắt đầu từ phần tử đầu tiên của mảng A, so sánh từng phần tử với x. Khi đến phần tử thứ tám sẽ thấy giá trị 20. Đó là tìm kiếm tuần tự.

b) Giả sử tập hợp A được tổ chức thành một cây tìm kiếm nhị phân, ta sẽ bắt đầu từ nút gốc và so sánh x với giá trị của nút:

• Nếu x < giá trị nút gốc: Di chuyển sang nút con bên trái.
• Nếu x > giá trị nút gốc: Di chuyển sang nút con bên phải.

BÀI 2.3:

CÂY TÌM KIẾM

NHỊ PHÂN

NỘI DUNG BÀI HỌC

1

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

2

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

KHÁI NIỆM CÂY TÌM KIẾM

NHỊ PHÂN

PHẦN 1

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 hơn 40 nằm ở đâu trên cây nhị phân?

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.

Quan sát Hình 2 và trả lời câu hỏi:

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 đá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.

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

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

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

• 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

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

Giá trị của nút có chỉ số i được lưu trữ vào phần tử T[i].

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

Hoạt động Làm tr.41 SGK

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

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).

Cây tìm kiếm nhị phân là cây nhị phân, trong đó, giá trị khoá của nút bất kì luôn lớn hơn giá trị khoá của tất cả nút thuộc cây con trái và nhỏ hơn giá trị khoá của tất cả nút thuộc cây con phải.

GHI NHỚ

MÔ PHỎNG THUẬT TOÁN

TẠO CÂY TÌM KIẾM NHỊ PHÂN

PHẦN 2

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.

THẢO LUẬN NHÓM

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.

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?

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

biểu diễn một tậ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.

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

biểu diễn một tập số nguyên dương

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

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

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.

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

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

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

• 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

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

• 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 là nút lá.

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.

Có nhiều 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.

GHI NHỚ

LUYỆN TẬP

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

A. Mọi nút thuộc cây con phải

của nút gốc có khoá nhỏ hơn khoá nút gốc.

B. Mọi nút thuộc cây con trái

của nút gốc có khoá lớn hơn

khóa nút gốc.

C. Cây rỗng không phải là cây

tìm kiếm nhị phân.

D. Cả cây con trái và cây con phải của nút gốc đều là cây tìm kiếm nhị phân.

D. Cả cây con trái và cây con phải của nút gốc đều là cây tìm kiếm nhị phân.

Câu 1. Phát biểu nào sau đây về cây tìm kiếm nhị phân là ĐÚNG?

A. 2.

B. 3.

C. 4.

D. 5.

C. 4.

Câu 2. Em cần thực hiện bao nhiêu bước để tìm kiếm nút có giá trị khoá bằng 7 trên cây tìm kiếm

nhị phân sau đây?

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