II. CÂY (TREE)
1. Các khái niệm cơ bản:
Đònh nghóa: Đồ thò vô hướng, liên thông và không chứa chu trình đơn nào gọi là cây.
Vì cây không chứa chu trình đơn nên nó không thể có cạnh bội và vòng. Vì vậy cây là
một đồ thò đơn.
Ví dụ:
(hình 1)
Nếu một đồ thò vô hướng, không chứa chu trình đơn nào nhưng không liên thông thì đồ
thò đó phải chứa các thành phần liên thông. Ta sẽ gọi loại đồ thò đó là rừng.
Ví dụ:
(Hình 2: Một rừng với 5 thành phần liên thông)
Đònh lý: Một đồ thò vô hướng là một cây nếu và chỉ nếu tồn tại một đường đi duy nhất
giữa mọi cặp đỉnh bất kì của nó.
Chứng minh:
- Giả sử đồ thò vô hướng T là một cây. Cho x và y là hai đỉnh bất kì của T. Vì T liên
thông nên phải có một đường đi
α
từ x đến y. Nếu có một đường đi
β
(khác
α
) từ x đến y thì
cặp (
α
,
β
) sẽ tạo thành một chu trình đơn. Mâu thuẩn với giả thiết T là một cây.
- Ngược lại giả sử đồ thò vô hướng T thỏa tính chất tồn tại một đường đi duy nhất giữa
mọi cặp đỉnh bất kì của nó. Ta suy ra được:
1. T liên thông.
2. Nếu tồn tại một chu trình đơn trong T. Chẳng hạn chu trình đơn chứa hai đỉnh x, y nào

QED
o Một số ứng dụng:
Cây được sử dụng trong rất nhiều lónh vực, đặc biệt là trong các mô hình liên quan đến
cấu trúc tổ chức của các đối tượng đang được xét đến:
119
o Hệ thống folder trong các máy tính:
Người ta tổ chức quản lí tài nguyên của hệ thống máy tính theo các folder. Mỗi folder
có thể chứa các folder con hoặc không. Loại folder không thể chứa các folder con gọi là các
file.
Một Folder gốc chứa toàn bộ các folder khác gọi là Desktop . Trong hình trên là một
phần hình ảnh trích từ giao diện của Windows Explorer (MicroSoft Windows 98). Một nhánh
của cây quản lí tài nguyên trên là:
Desktop
My Computer My Documents
A:\ C:\
Hp_xtra Register
Sku.11 t_drive.GDI
o Cây tìm kiếm nhò phân.
Bài toán tìm kiếm các mục thông tin trong một danh sách là một trong các bài toán
quan trọng của tin học. Thuật toán tìm kiếm sẽ có hiệu quả nhất khi các mục thông tin đó được
sắp xếp có thứ tự. Trong trường hợp các mục thông tin đó được sắp xếp theo các đỉnh của của
120
một cây nhò phân thì mỗi đỉnh sẽ được gán cho một khóa sao cho khóa của mỗi đỉnh đều lớn
hơn bất kì khóa nào của các đỉnh thuộc cây con bên trái của đỉnh đó và nhỏ hơn bất kì khóa
nào của các đỉnh thuộc cây con bên phải của đỉnh đó.
Giải thuật xây dựng các mục thông tin trên cây nhò phân có thể được phát biểu một
cách đệ qui như sau:
Bắt đầu với một cây chỉ chứa một đỉnh (tức là gốc). Mục thứ nhất trong danh sách sẽ
được gán làm khóa cho gốc đó. Để bổ sung một mục thông tin mới, trước hết so sánh nó với
các khóa của các đỉnh đã có trên cây, bắt đầu từ gốc đi sang trái nếu mục thông tin đó có khóa

IF (Con bên phải của v
≠
Null) THEN v:= Con bên phải của v
ELSE Thêm đỉnh mới u là con bên phải của v và gán v:= Null
END
IF (Gốc cuả T = Null) THEN Thêm đỉnh r vào cây và gán cho nó khóa X
ELSE IF (Khóa(v)
≠
x) THEN Gán cho đỉnh mới u khóa X
ELSE Return(v)
o Cây quyết đònh.
Cây có gốc, trong đó mỗi đỉnh tương ứng với một quyết đònh và mỗi cây con của cây
này tương ứng với một phương án có thể có của một quyết đònh. Những lời giải có thể có của
bài toán tương ứng với các đường đi tới các lá.
o Mã Huffman.
Giả sử ta muốn gởi một thông báo bao gồm một dãy các kí tự. Trong mỗi thông báo các
kí tự là độc lập với nhau và xuất hiện với xác suất đã biết tại bất kì vò trí nào của thông báo.
Chẳng hạn, ta muốn gởi một thông báo chỉ gồm 5 kí tự a, b, c, d, e với xác suất xuất hiện lần
lượt là 0.12, 0.4, 0.15, 0.08, 0.25. Ta muốn mã hóa các kí tự đó bằng mã nhò phân 0 và 1 sao
cho không có mã hóa của kí tự nào là phần đầu (ie: trùng với) của mã hóa của các kí tự còn lại
(Gọi là điều kiện tiền tố).
Ví dụ
1
ta có hai cách mã hóa sau đây:
Kí tự Xác suất Code 1 Code 2
a 0.12 000 000
b 0.40 001 11
c 0.15 010 01
d 0.08 011 001
e 0.25 100 10