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

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

KHỞI ĐỘNG

Em hãy đưa ra danh sách giá trị khoá các nút ở cây nhị phân (Hình 1) trong phép duyệt cây theo thứ tự giữa và nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra này.

Hình 1. Ví dụ cây nhị phân

• Dãy giá trị đưa ra được sắp xếp tăng dần: 1, 2, 3, 4, 5, 6.
• Cây có đặc điểm là mỗi nút trong có giá trị khoá lớn hơn giá trị khoá nút con trái và nhỏ hơn giá trị khoá nút con phải.

Hình 1. Ví dụ cây nhị phân

KHỞI ĐỘNG

BÀI 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

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

3

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

4

Sắp xếp dựa trên 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

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

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

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.

Cách tham gia

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

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

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à đặt 4 câu hỏi là xác định được vị trí nút có giá trị khoá 55.

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

“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

Trả lời

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

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

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

“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

Trả lời

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

“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 → 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, tiếp tục với nút gốc của cây con phía không bị bỏ qua.

Áp dụng được trên cây có cấu trúc 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à phải của nút gốc cũng là cây tìm kiếm nhị phân.

XÂY DỰNG

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

PHẦN 2

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.

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

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:

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

2. Xây dựng 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

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

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

Lưu ý

Để dễ kiểm soát: 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.

2. Xây dựng cây tìm kiếm nhị phâ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.

2. Xây dựng cây tìm kiếm nhị phâ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

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

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.

THỰC HÀNH

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

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.

THỰC HÀNH

• Chèn 28 như là nút con trái.

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.

TÌM KIẾM NÚT TRÊN

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

PHẦN 3

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

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?

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:

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.

Cây rỗng

Trái lại

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.

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

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

------------------------------

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