Tin học 12 · SGK Chuyên đề Khoa học máy tính

Bài 9. Các thuật toán duyệt trên cây tìm kiếm nhị phân

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

Sau bài học này em sẽ:

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:

1. Các thuật toán duyệt cây tìm kiếm nhị phân

Hoạt động 1

Quan sát cách cài đặt các thuật toán duyệt trên cây tìm kiếm nhị phân và trao đổi về ý nghĩa và sự khác biệt khi thực hiện các thuật toán này so với các thuật toán duyệt cây nhị phân đã học trong Bài 6.

Từ Bài 6 chúng ta đã biết ba phương pháp duyệt cây nhị phân là duyệt trước, duyệt sau và duyệt giữa được cài đặt trên cây nhị phân hoàn chỉnh biểu diễn một chiều (kiểu dữ liệu list của Python). Để thực hiện các thuật toán này trên cây tìm kiếm nhị phân, cần nhớ lại cây tìm kiếm nhị phân muốn biểu diễn một chiều cần bổ sung thêm các nút None để trở thành cây nhị phân hoàn chỉnh trước khi có thể biểu diễn bằng mảng. Do vậ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 k < len(T) và T[k] != None để nút tại chỉ số k không là nút giả None.

Sau đây là các hàm duyệt cây tìm kiếm nhị phân. Chương trình in ra các khoá của các nút đã duyệt.

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

Thuật toán duyệt trước bắt đầu từ nút k:

def preorder(T, k):
if k < len(T) and T[k] != None:
print(T[k], end = " ")
preorder(T, left(k))
preorder(T, right(k))

Lệnh duyệt trước toàn bộ cây tìm kiếm nhị phân T là:

preorder(T,0)

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

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

def postorder(T, k):
if k < len(T) and T[k] != None:
postorder(T, left(k))
postorder(T, right(k))
print(T[k], end = " ")

Lệnh duyệt sau toàn bộ cây tìm kiếm nhị phân T là:

postorder(T,0)

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

Thuật toán duyệt giữa bắt đầu từ nút k:

def inorder(T, k):
if k < len(T) and T[k] != None:
inorder(T, left(k))
print(T[k], end = " ")
inorder(T, right(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à:

inorder(T,0)

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

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

def reverseorder(T, k):
if k < len(T) and T[k] != None:
reverseorder(T, right(k))
print(T[k], end = " ")
reverseorder(T, left(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 khoá.

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à:

reverseorder(T,0)

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

2. Sắp xếp dãy số bằng cây tìm kiếm nhị phân

Hoạt động 2

Trao đổi, thảo luận để giải bài toán sau:

Cho trước dãy số A. Thiết kế thuật toán sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.

Bài toán sắp xếp các phần tử của một dãy số đã được trình bày trong các thuật toán sắp xếp; ví dụ:

Có một cách sắp xếp khác sử dụng cây tìm kiếm nhị phân. Cách này thực hiện dựa trên các thuật toán duyệt trên cây tìm kiếm nhị phân. Đoạn mã giả của thuật toán sắp xếp như sau:

1. BSTSort(A)
2. Thiết lập cây tìm kiếm nhị phân T từ dãy A.
3. Thực hiện thuật toán duyệt giữa (inorder) theo thứ tự tăng dần, cập nhật các thay đổi vào dãy A.

Theo định nghĩa thì cây tìm kiếm nhị phân không cho phép khoá trùng nhau; do vậy nếu thực hiện theo đúng thuật toán đã mô tả trên thì sẽ chỉ sắp xếp được các phần tử khác nhau của dãy A. Muốn xử lí chính xác các khoá trùng nhau của cây tìm kiếm nhị phân, chúng ta sẽ cần thêm công cụ để xử lí trường hợp khoá trùng nhau trên cây tìm kiếm nhị phân T. Có nhiều cách xử lí yêu cầu này; ví dụ:

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.

Chúng ta sẽ thiết lập theo cách 2.

Với cây nhị phân được hiểu theo cách mới cho phép các khoá trùng nhau thì thuật toán chèn khoá hoàn toàn tương tự thuật toán đã trình bày trong Bài 7, chỉ có một điểm khác biệt duy nhất là chương trình sẽ không dừng lại khi gặp trường hợp khoá trùng. Hàm chèn khoá v vào cây tìm kiếm nhị phân T sẽ như sau:

def Tree_Insert(T, v):
k = 0
while k < len(T) and T[k] != None:
if v < T[k]:
k = left(k)
else:
k = right(k)
if k >= len(T):
T.extend([None] * (k - len(T) + 1))
T[k] = v

Chúng ta cần 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.

def new_inorder(T, k, A):
if k < len(T) and T[k] != None:
new_inorder(T, left(k), A)
A.append(T[k])
new_inorder(T, right(k), A)

Đ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 như sau. Chương trình sẽ sử dụng thư viện cây tìm kiếm nhị phân BST.py.

from BST import *
def BSTSort(A):
T = []
for x in A:
Tree_Insert(T, x)
A.clear()
new_inorder(T, 0, A)

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.