Bài 7. Cây tìm kiếm nhị phân

1. Cây tìm kiếm nhị phân

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

Quan sát các cây nhị phân sau, em có nhận xét gì về giá trị của các nút trên cây?

Gợi ý: Tại mỗi nút, so sánh dữ liệu của các nút của cây con trái và của cây con phải với nút này.

Cây tìm kiếm nhị phân (BST – Binary Search Tree) là một dạng đặc biệt của cây nhị phân thông thường, được tạo ra với mục đích hỗ trợ thuận tiện cho các bài toán tìm kiếm, chèn, xoá, sắp xếp.

Hoạt động 1. Tìm hiểu cấu trúc cây tìm kiếm nhị phân

Tìm hiểu và thảo luận về tổ chức dữ liệu của cây nhị phân và cây tìm kiếm nhị phân.

a) Mô hình dữ liệu cây nhị phân

Mô hình nút liên kết của cây nhị phân sẽ bao gồm:

Có thể tổ chức dữ liệu cây nhị phân theo hai cách là sử dụng mô hình nút liên kết hoặc mảng một chiều:

Hình 7.2. Mô hình nút liên kết cây nhị phân

Trong bài học trước, chúng ta đã biết cách biểu diễn cây nhị phân hoàn chỉnh bằng mảng một chiều và có thể biến đổi cây nhị phân tổng quát thành cây nhị phân hoàn chỉnh đã biến đổi bằng cách thêm các nút giả None. Cây nhị phân hoàn chỉnh đã biến đổi cũng có thể được cài đặt bằng mảng một chiều tương tự như cây nhị phân hoàn chỉnh. Theo cách biểu diễn này, mọi cây nhị phân T đều có thể biểu diễn bằng mảng, dãy các phần tử chính là các giá trị (khoá) của các nút của cây T. Nút gốc ứng với T[0] của mảng.

Cây nhị phân tổng quát ở Hình 7.3c được thêm vào các nút giả None để trở thành cây nhị phân hoàn chỉnh và được cài đặt bằng mảng T = [5, 3, 7, None, None, 6].

Cây nhị phân trong Hình 7.3b được cài đặt bằng mảng T = [5, 3, 7, 6].

Hình 7.3. Biểu diễn cây nhị phân bằng mảng

Để thiết lập cây nhị phân rỗng, chúng ta sử dụng hàm sau:

def Tree():
return []

Các hàm left(k), right(k) và parent(k) trả về chỉ số của nút con trái, nút con phải, nút cha của nút có chỉ số k.

def left(k):
return 2*k+1
def right(k):
return 2*k+2
def parent(k):
return (k-1)//2

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

Cây tìm kiếm nhị phân là cây nhị phân, có hai tính chất quan trọng:

Cây cân bằng: cây tìm kiếm nhị phân mà tại mọi nút thì chiều cao của cây con trái và của cây con phải lệch nhau nhiều nhất là 1 (Hình 7.4a). Cây này được gọi là cây cân bằng. Đây là trường hợp tốt nhất, tốn ít thời gian để tìm kiếm một khoá trên cây này; thuật toán tìm kiếm là tìm kiếm nhị phân.

Cây suy biến: cây tìm kiếm nhị phân có chiều cao lớn nhất, mỗi nút chỉ có tối đa một nút con. Cây này được gọi là cây suy biến. Đây là trường hợp xấu nhất, tốn nhiều thời gian để tìm kiếm một khoá trên cây này; thuật toán tìm kiếm là tìm kiếm tuần tự.

Hình 7.4. Cây tìm kiếm nhị phân

Khi cây tìm kiếm nhị phân được cài đặt bằng mảng T, tại mọi nút k, với mọi nút i thuộc cây con trái và với mọi nút j thuộc cây con phải, ta có bất đẳng thức: T[i] < T[k] < T[j]

Lưu ý: Nếu cây nhị phân T là cây tìm kiếm nhị phân thì mọi cây con của T cũng là cây tìm kiếm nhị phân.

Cây tìm kiếm nhị phân là cây nhị phân mà tại mọi nút, khoá của nút này lớn hơn khoá của các nút con thuộc cây con trái và nhỏ hơn khoá của các nút con thuộc cây con phải. Khoá của các nút là duy nhất, nghĩa là hai nút khác nhau có khoá khác nhau.

2. Thuật toán chèn khoá mới vào cây tìm kiếm nhị phân

Hoạt động 2. Thuật toán chèn khoá mới vào cây tìm kiếm nhị phân

Bài toán: Cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân. Quan sát, thảo luận, tìm hiểu thuật toán tìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.

Quá trình chèn khoá v = 7 vào cây tìm kiếm nhị phân T ở Hình 7.6a như sau:

Bước 1. Tìm vị trí cần chèn khoá v trên cây T (Hình 7.6b). Khoá v lớn hơn khoá 5, đi đến nút con phải. Khoá v nhỏ hơn khoá 10, đi đến nút con trái. Khoá v nhỏ hơn khoá 8, đi đến nút con trái và gặp nút giả None.

Bước 2. Chèn khoá v vào cây T (Hình 7.6c). Trong trường hợp khoá v không có trong cây T thì chèn khoá v vào cây này bằng cách tạo nút thật mới tại nút giả None và gán khoá v cho nút mới này.

c) Chèn khoá mới vào cây tìm kiếm nhị phân

Quá trình chèn một khoá v vào cây tìm kiếm nhị phân T gồm hai bước: Bước 1. Tìm vị trí chính xác cần chèn. Nếu gặp khoá v thì dừng chương trình. Bước 2. Thực hiện thao tác chèn.

Hàm Tree_Insert(T, v) dùng để chèn khoá v vào cây tìm kiếm nhị phân T được cài đặt bằng một danh sách (thuộc kiểu list của Python). Bước 1 thực hiện tìm vị trí cần chèn khoá v bắt đầu từ nút gốc T[0] cho đến khi gặp nút giả T[k] = None hoặc tìm thấy nút T[k] = v thì kết thúc. Bước 2 thực hiện chèn khoá v vào cây T tại nút k. Nếu k ≥ len(T) thì ta phải thêm các nút None từ chỉ số len(T) đến chỉ số k để cây T là cây nhị phân hoàn chỉnh. Số nút giả None thêm vào là k - len(T) + 1.

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

Bước 1. Tìm vị trí cần chèn. Xuất phát từ gốc, đi theo các nút cho đến khi gặp nút rỗng. Nếu gặp nút có khoá thì chương trình dừng. Bước 2. Thực hiện thao tác chèn, đặt v vào phần tử thứ k.

Đoạn chương trình sau thực hiện việc tạo cây tìm kiếm nhị phân từ một tập hợp các phần tử cho trước.

A = [7, 1, 9, 0, 5, 10, 2]
T = Tree()
for x in A:
Tree_Insert(T, x)

3. Thuật toán tìm kiếm trên cây tìm kiếm nhị phân

Hoạt động 3. Tìm hiểu thuật toán tìm kiếm trên cây tìm kiếm nhị phân

Quan sát quá trình tìm kiếm khoá trên cây tìm kiếm nhị phân thông qua các ví dụ

Chúng ta sẽ thiết lập chương trình tìm kiếm một nút với khoá v. Quá trình tìm kiếm được thực hiện bắt đầu từ nút có chỉ số k trên cây tìm kiếm nhị phân T. Nếu tìm thấy thì hàm trả về chỉ số của nút có giá trị v, ngược lại trả về -1.

Từ suy luận trên, chúng ta thiết lập được hai cách tìm kiếm, một cách sử dụng kĩ thuật đệ quy và một cách không sử dụng kĩ thuật đệ quy. Cả hai cách này đều có độ phức tạp thời gian O(h) với h là chiều cao của cây tìm kiếm nhị phân.

Hàm tìm kiếm sử dụng đệ quy:

def search(T, k, v):
if k >= len(T) or T[k] == None:  # Nút T[k] là nút giả
return -1
else:
if v == T[k]:  # Tìm thấy khoá v
return k  # Trả về chỉ số
elif v < T[k]:
return search(T, left(k), v)  # Tìm khoá v trên cây con trái
else:
return search(T, right(k), v)  # Tìm khoá v trên cây con phải

Hàm tìm kiếm không sử dụng kĩ thuật đệ quy:

def search(T, k, v):
while k < len(T) and T[k] != None and T[k] != v:
if v < T[k]:
k = left(k)  # k đến nút con trái
else:
k = right(k)  # k đến nút con phải
if k >= len(T) or T[k] == None:  # Không tìm thấy khoá
return -1
else:  # Tìm thấy khoá
return k  # Trả về chỉ số nút

k = search(T, 0, v)  # Tìm khoá v trên cây tìm kiếm nhị phân T
if k >= 0:
print("Tìm thấy nút có khoá", T[k])
else:
print("Không tìm thấy khoá", v)

Thuật toán tìm kiếm khoá K trong cây tìm kiếm nhị phân có độ phức tạp thời gian O(h), với h là chiều cao của cây; tương đương với O(logn) trong trường hợp trung bình hay O(n) trong trường hợp xấu nhất.

LUYỆN TẬP

VẬN DỤNG

Ví dụ:

Dãy [10, 7, 0, 5, None, 3] là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi.

Dãy [1, 6, None, 2, 3, None, 4] không là biểu diễn của cây nhị phân tổng quát nào.

Ví dụ:

Dãy [5, 3, 6, None, 4, None, 10] là biểu diễn của cây tìm kiếm nhị phân.

Dãy [2, 1, 5, None, 3, 4, 10] không là biểu diễn của cây tìm kiếm nhị phân (mặc dù dãy này là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi).

Data.inp

Nguyễn Văn Năm 9.3, Bùi Văn Hai 9.0, Trần Quang Bảy 8.8