Luận văn tốt
56
Chương 5
MỘT SỐ VẤN ĐỀ VỀ CÂY
I. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN
1. Định nghĩa Cho đồ thị
G = <X, U>
, G được gọi là một cây nếu G liên thông
và không có chu trình, ở đây n =

X

> 1.
Khi đó sáu tính chất sau là tương đương
1) G là đồ thị liên thông và không có chu trình
2) G không có chu trình và có n - 1 cạnh
3) G liên thông và có n - 1 cạnh
4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì
G xuất hiện duy nhất một chu trình.
5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được sẽ không liên
thông.
6) Mỗi cặp đỉnh trong G được nối với nhau bằng một đường duy nhất.
Chứng minh:
Ta chứng minh theo trình tự sau:
1)

3): Giả sử G không có chu trình và n - 1 cạnh ta chứng minh 3)
Thật vậy, giả sử ngược lại G không liên thông, khi đó p

2 . Từ 2) ta có v(G)
= m - n + p = 0 và m = n -1, kết hợp ta có (n - 1) - n + p = 0 hay p = 1, trái với
giả thiết p

2. Vậy G liên thông và số cạnh là n -1.
3)

4): Giả sử G là liên thông và có n - 1 cạnh, ta chứng minh 4).
Thật vậy vì G liên thông nên p = 1, mặt khác m = n - 1 nên v(G) = m - n + 1 = 0
hay G không có chu trình . Nếu thêm vào G một cạnh thì ta được đồ thị G' với
số cạnh là n, hay v(G') = n - n + 1 = 1 hay G' có một chu trình.
4)

5): Giả sử ngược lại G không liên thông, tức là tồn tại cặp đỉnh x, y trong
G mà không có đường nào nối x với y. Khi đó nối x và y bởi 1 cạnh, đồ thị nhận
được vẫn không có chu trình điều này mâu thuẫn với 4). Hay G là liên thông.
Luận văn tốt
57
Nếu bỏ đi 1 cạnh trong G mà đồ thị vẫn liên thông thì nếu khôi phục lại cạnh
này đồ thị sẽ có chu trình. Điều này mâu thuẫn với 4). Vậy ta có 5).
5)

6): Giả sử ngược lại, nếu trong G có tồn tại cặp đỉnh x, y không nối với
nhau bằng đường nào cả, chứng tỏ G không liên thông mâu thuẫn với 5). Vậy
T T'
Hình 1.1

a
b
d
i
j
e
h

k
c

g

f
h
a

d

i

j

4. Các ứng dụng
4.1 Mã tiền tố
Kỹ thuật nén và mã hoá là 1 trong những lĩnh vực thường hay được sử dụng
trong Tin học, cây nhị phân có nhiều ứng dụng trong việc nghiên cứu áp dụng
các giải thuật trong lĩnh v
ực vực này. Một trong những ứng dụng của cây nhị
phân đó là mã tiền tố. Ví dụ mã tiền tố như là dùng các xâu nhị phân có độ dài
khác nhau để mã các ký tự để không có xâu nhị phân nào ứng với hơn một chữ
cái. Trên cây nhị phân mã hoá, các lá là các ký tự cần mã hoá và đường đi từ
cha đến con trái là 1 (hoặc 0), còn đi tới con phải là 0 (hoặc 1). Quá trình mã
hoá sẽ duyệt cây đó từ gốc tới lá, khi tới nút con sẽ tạo ra một bít 0 ho
ặc 1 và tới
nút lá sẽ tạo ra một xâu bít. Do vậy, mã sinh ra cho một ký tự sẽ không là phần
đầu của ký tự khác.
Hình 1.2

Ví dụ như hình 1.2 cây nhị phân biểu diễn mã tiền tố của các ký tự a, e, i, k, o,
p, u trong đó:
a : 000 k : 1100 u : 11111
e : 001 o : 1101
i : 01 p : 11110
0
0
0

hiện của các ký tự. Quá trình mã hoá và giải mã phụ thuộc vào việc xây dựng
cây nhị
phân mã hoá. Thuật toán Huffman tạo cây nhị phân từ nút lá đến nút
gốc, ký tự nào có tần số càng cao thì nút lá tương ứng càng gần gốc hơn.
Thuật toán:
Vào: Bảng tần số xuất hiện các ký tự sắp xếp giảm dần
Ra : Cây nhị phân biểu diễn mã, nhánh phải là 1, trái là 0.
Bước 1: Lấy hai phần tử cuối bảng tần số xuất hiện ra khỏi bảng
Bước 2: Nếu phần t
ử nào chưa nằm trong cây nhị phân thì tạo ra một nút lá
chứa phần tử đó, phần tử này chính là ký tự. Nối hai nút tương ứng với hai phần
tử này với nhau thông qua việc tạo nút cha của chúng. Phần tử có tần số xuất
hiện lớn hơn là nút trái, nhỏ hơn là nút phải.
Bước 3: Tính tổng tần số xuất hiện của 2 phần tử này chèn vào bảng sao cho
phù hợp với nguyên tắc giả
m dần của bảng. Phần tử mới của bảng sẽ tương ứng
với nút vừa được tạo ra ở bước 2.
Bước 4: Quay trở lại bước 1 đến khi bảng chỉ còn lại 1 phần tử. Phần tử cuối
cùng tương ứng với nút gốc của cây nhị phân.

Ví dụ: Ta có kết quả mã Huffman cho các ký tự ở bảng sau:

Ký tự Tần suất Mã nhị phân Chiều dài mã
a 0.3 00 2
b 0.2 10 2
c 0.2 11 2
d 0.1 011 3
e 0.1 0100 4
f 0.1 0101 4


end;
Var a:array[1..n] of Nod;
i,m:integer;
Procedure InputData; {Khởi tạo bảng tần suất các ký tự}
Var i:integer;
begin
for i:=1 to n do with A[i] do
begin S:=Round(exp(n/5)/exp(i/5))+1;Name:=Char(64+i);Code:=''; end;
end;
Procedure FindCode(m:integer); {Sinh mã huffman}
Var y,z:nod;
k:integer;
Begin
if m=1 then exit;
y:=a[m-1];
a[m-1].s:=a[m-1].s+a[m].s;
k:=m-1;
While (k>1) and (a[k].s>a[k-1].s) do Begin
a,e,f,d,b,c
a,e,f,d b,c
e,f,da

e,f
d
e

f
b
c


z:=a[k]; a[k]:=a[k-1]; a[k-1]:=z; k:=k-1;
End;
FindCode(m-1);
z:=a[k];
for i:=k to m-2 do a[i]:=a[i+1];
a[m-1]:=y;
a[m-1].code:=z.code+'1'; a[m].code:=z.code+'0';
End;

BEGIN
InputData; FindCode(n);
For i:=1 to n do writeln(a[i].code);
END.

4.2 Cây biểu diễn biểu thức
Một biểu thức toán học có thể biểu diễn bằng cây, đây cũng là vấn đề hữu ích
trong việc xử lý và lưu trữ biểu thức toán học trong máy tính
Xét biểu thức đại số sau:
Có thể vẽ 1 cây nhị phân như hình 1.4 biểu diễn biểu thức A, trong đó mỗi đỉnh
trong mang dấu của một phép tính, gốc của cây mang phép tính sau cùng của A,
ở đ
ây là dấu nhân ký hiệu: *, mỗi lá mang 1 số hoặc một chữ đại diện cho số.
Hình 1.4



62
Bằng duyệt cây ta có thể tính được giá trị biểu thức, ngoài phương pháp tiền
thứ tự còn có thể duyệt cây theo phương pháp pháp khác để tính giá trị biểu
thức tùy vào yêu cầu và đặc điểm của từng bài toán.

4.3 Cây quyết định
Có những bài toán phụ thuộc vào các quyết định. Mỗi quyết định thì có thể có
nhiều kết cục và những kết cục cuối cùng chính là lời giải của bài toán. Để giải
nh
ững bài toán như vậy, người ta biểu diễn mỗi quyết định bằng một đỉnh của
đồ thị và mỗi kết cục là 1 lá của quyết định. Một cây được xây dựng như trên
gọi là cây quyết định. Trong nhiều bài toán Tin gặp phải, có thể dùng cây quyết
định để mô hình hoá từ đó việc cài đặt sẽ dễ dàng thuận tiện hơn.

Ví dụ:
hình 1.5 là cây quyết định biểu di
ễn việc sắp xếp 3 số khác nhau a, b, c

Hình 1.5


a<c
Luận văn tốt
63
If Can(a,b) then Begin
If Can(a,c) then Begin
if Can(b,c) then Writeln(c,' ',b,' ',a)
Else Writeln(b,' ',c,' ',a);
End
Else Writeln(b,' ',a,' ',c);
End
Else Begin
If Can(b,c) then Begin
if Can(a,c) then Writeln(c,' ',a,' ',b)
Else Writeln(a,' ',c,' ',b);
End
Else Writeln(a,' ',b,' ',c);
End;
End.4.4 Cây sắp xếp và tìm kiếm
Sắp xếp và tìm kiếm là một trong những vấn đề cơ bản trong kỹ thuật lập trình,
cây nhị phân cũng có khá nhiều ứng dụng quan trọng trong vấn đề này. Ta có
thể mô hình hoá việc sắp xếp và tìm kiếm bằng cây từ đó ta có thể đánh giá các
kỹ thuật này từ góc độ về cây.

4.4.1 Sắp xếp chèn với tìm kiếm nhị phân
Hình 1.6
b) Sắp xếp chèn bằng việc tìm nhị phân vị trí đúng.
Có thể tạm gọi là phương pháp sắp xếp chèn nhị phân. Ý tưởng như sau: cho
trước một danh sách đã sắp xếp A, cần chèn 1 phần tử m
ới x vào A sao cho
danh sách luôn được sắp xếp. Đầu tiên ta tìm vị trí đúng của x trong A sau đó
chèn x vào đúng vị trí này trong A, ta có danh sách A = A

{x} luôn được sắp
xếp. Để tìm được ví trí đúng cần chèn của x trong A ta sử dụng phương pháp
tìm kiếm nhị phân, chèn theo cách này gọi là chèn nhị phân.
Ví dụ để sắp xếp B = x
1
, x
2
, x
3
, ... x
n
ta thực hiện như sau:
A := 
For i:=1 to n do Begin
- Tìm vị trí đúng của x
i
trong A theo phương pháp tìm nhị phân
- Chèn x
i
vào A theo đúng vị trí vừa tìm được (A := A


65
Repeat
t:= (l + r) div 2;
If Pt = ds[t] then Begin FindNp:=t+1; Exit End
Else If Pt<ds[t] then r:=t
Else l:=t;
Until r=l+1;
FindNp:=l+1;
End;
End;
Var i, j, vt, s: Integer;
Begin
For i:=2 to n do Begin
vt:= FindNp(1,i-1,ds[i]);
{Chen dung vi tri sao cho ds luon duoc sap xep}
s:=ds[i];
For j:=i-1 Downto vt do ds[j+1]:=ds[j];
ds[vt]:=s;
End;
For i:=1 to n do Write(ds[i]:3);
End.

4.4.2 Thuật toán sắp xếp hoà nhập
Giả sử ta có danh sách chưa được sắp 8, 2, 4, 6, 9, 7, 10, 1, 5 ,3 có thể dùng
cây nhị phân mô tả quá trình sắp xếp danh sách theo thứ tự tăng dần như sau:
Cây nhị phân với gốc được gán là chính là danh sách đó. Các con của gốc
được gán theo nguyên tắc: Con bên trái gán nửa danh sách đầu, con bên phải
gán nửa danh sách còn lại (danh sách gán ở gốc cây con trái và cây con phải
hoặc bằng nhau về số lượng hoặc chênh lệch nhau 1 phần tử).