Cấu trúc dữ liệu và giải thuật

ó 8 cây 1 đỉnh, hình 13.4a. Thực hiện các phép hợp Union(0, 1), 
Union(2, 3), Union(4, 5), Union(6, 7) ta thu được các cây trong hình 13.4b. 
Thực hiện tiếp các phép hợp Union(0, 2), Union(4, 6) ta nhận được các cây 
trong hình 13.4c. Cuối cùng thực hiện phép hợp Union(0, 4) ta nhận được 
cây hình 13.4d. Cây này có độ cao 4 = ⎣log8⎦ + 1. 
(a) 
(b) 
(c) 
0 1 2 3 4 5 6 7
0 
1 
2 4 6
3 5 7
0
1 2 
3 
4
5 6
7
 360
(d) 
 Hình 13.4. Cây trong trường hợp xấu nhất được tạo thành 
 từ dãy phép hợp theo trọng số 
Từ định lý 13.1 ta suy ra rằng, nếu sử dụng phép hợp theo trọng số, thì thời 
gian thực hiện phép tìm trong trường hợp xấu nhất là O(logn), trong đó n là 
số phần tử của tập vũ trụ. Nếu chúng ta tiến hành một dãy phép toán gồm n 
phép hợp và m phép tìm, thì thời gian trong trường hợp xấu nhất là 
O(mlogn). 
Thay cho việc lưu trọng số của các cây, chúng ta có thể lưu độ cao của 
các cây và thực hiện phép hợp theo độ cao (union-by-height). Bạn đọc hãy 
đưa ra quy tắc thực hiện phép hợp theo độ cao và chứng minh khẳng định 
tương tự như trong định lý 13.1. 
Một câu hỏi được đặt ra là, liệu có thể cải thiện thời gian thực hiện 
phép tìm được nữa không? Thật đáng ngạc nhiên, câu trả lời là có. 
13.3.2 Phép tìm với nén đường 
Nhằm cải thiện hơn nữa thời gian thực hiện phép tìm, khi thực hiện 
một phép tìm chúng ta sẽ thực hiện kèm theo một hành động được gọi là nén 
đường (path-compression). Khi biểu diễn một tập con bởi cây với phần tử 
đại biểu của tập được chứa trong gốc của cây, để thực hiện phép tìm Find(a) 
chúng ta cần phải đi từ đỉnh a theo các con trỏ lên gốc cây. Đường từ a lên 
gốc cây được gọi là đường tìm, chẳng hạn, nếu thực hiện Find(7) trong cây 
hình 13.4d thì đường tìm là 7 – 6 – 4 – 0. 
Nén đường có nghĩa là, khi thực hiện phép tìm Find(a), chúng ta thay 
đổi tất cả các con trỏ nằm trên đường tìm từ a lên gốc, cho chúng trỏ tới gốc 
0
1 2 4
3 5 6
7
 361
cây. Nén đường được minh hoạ trong hình 13.5, đường tìm được tìm ra khi 
thực hiện Find(a) được chỉ ra trong hình 13.5a, cây thu được sau khi nén 
đường được cho trong hình 13.5b. 
 (a) 
(b) 
Hình 13.5. (a) Cây trong đó Find(a) sinh ra một đường tìm. 
 (b) Cây kết quả sau khi nén đường. 
Cần lưu ý rằng, việc thực hiện nén đường kèm theo phép tìm không 
làm tăng thời gian thực hiện phép tìm, phép tìm vẫn chỉ đòi hỏi thời gian tỷ 
lệ với độ dài của đường tìm. Trực quan chúng ta thấy rằng, nén đường làm 
cho tất cả các đỉnh nằm trong các cây con gốc tại các đỉnh trên đường tìm trở 
nên gần gốc hơn. Chẳng hạn, các đỉnh trong các cây con T1, T2, T3 của cây 
e
d
c
b
a 
T5
T4
T3
T2
T1
e
dcba 
T5
T4T3T2T1
 362
trong hình 13.5b gần gốc hơn khi chúng ở trong cây hình 13.5a. Điều đó tạo 
điều kiện cho các phép tìm thực hiện sau sẽ hiệu quả hơn. 
Rõ ràng là việc thực hiện phép tìm với nén đường không ảnh hưởng gì 
đến thời gian thực hiện phép hợp. Thời gian chạy của phép hợp vẫn còn là 
O(1). Nếu phép hợp là phép hợp theo trọng số (hoặc phép hợp theo độ cao), 
phép tìm là phép tìm với nén đường, thì thời gian thực hiện phép tìm sẽ ra 
sao? Người ta đã chứng minh được rằng, thời gian chạy trả góp của phép tìm 
là rất gần O(1). Kết luận này được suy ra từ định lý sau đây. 
Định lý 13.2. Giả sử phép hợp theo trọng số và phép tìm với nén 
đường được thực hiện trên họ các tập con ban đầu gồm n tập một phần tử. 
Khi đó thời gian thực hiện một dãy m phép hợp và phép tìm, với m > n, là 
O(mlog*n), trong đó log*n là hàm được xác định như sau: 
log*n = min{i ≥ 0⎟ log(i)n ≤ 1} 
với log(i)n là 
log(i)n = log (log (… (logn))) 
 i lần 
Chứng minh định lý 13.2. là cực kỳ phức tạp, chúng ta không đưa ra ở 
đây. Để hiểu rõ bản chất của khẳng định trong định lý 13.2, chúng ta cần biết 
đặc điểm của hàm log*n. Hàm này tăng cực kỳ chậm. Bạn sẽ thấy được điều 
này qua một số giá trị của hàm: 
log*2 = 1 
log*4 = 2 
log*16 = 3 
log* 65536 = 4 
log* 265536 = 5 
Tức là để giá trị của hàm vượt quá 5 thì n cần phải lớn hơn 265536. Đây là con 
số cực kỳ khổng lồ, nó lớn hơn số các phần tử trong vũ trụ mà ta quan sát 
được! Đó là cơ sở để ta có thể xem rằng O(mlog*n) là O(m). 
13.4 ỨNG DỤNG 
Các phép toán hợp và tìm trên họ các tập không cắt nhau được sử 
dụng trong thiết kế và cài đặt nhiều thuật toán cho các vấn đề khác nhau, 
chẳng hạn thuật toán tìm cây bao trùm ngắn nhất của đồ thị vô hướng (thuật 
toán Kruskal), thuật toán tìm tổ tiên chung gần nhất của hai đỉnh bất kỳ 
trong một cây (thuật toán này rất quan trọng trong các áp dụng của lý thuyết 
 363
đồ thị, trong Biomformatics). Trong mục này chúng ta sẽ minh hoạ cách sử 
dụng phép hợp và phép tìm để thiết kế thuật toán thông qua hai áp dụng. 
13.4.1 Vấn đề tương đương 
Một quan hệ R trên tập S là một họ nào đó các cặp phần tử của S. Nếu 
cặp (a, b) ∈ R ta sẽ nói a có quan hệ R với b và ký hiệu aRb. Quan hệ R 
được gọi là quan hệ tương đương nếu nó thoả mãn các tính chất sau: 
• Tính phản xạ: aRa với mọi a ∈ S. 
• Tính đối xứng: aRb nếu và chỉ nếu bRa. 
• Tính bắc cầu: aRb và bRc kéo theo aRc. 
Chúng ta sẽ ký hiệu quan hệ tương đương bởi ~. Lớp tương đương 
của phần tử x ∈ S, ký hiệu là [x], gồm tất cả a ∈ S mà a ~ x (a tương đương 
với x). Dễ dàng chứng minh được rằng, các lớp tương đương tạo thành một 
phân hoạch của tập S. 
Đối với một quan hệ tương đương, vấn đề được đặt ra là: với hai phần 
tử bất kỳ a và b của S, chúng ta cần biết a có tương đương với b hay không? 
Nếu quan hệ tương đương đã hoàn toàn xác định trước, vấn đề được giải 
quyết rất đơn giản: đánh số của phần tử của S từ 0, 1, … đến n – 1, lưu quan 
hệ tương đương trong mảng boolean A[0… n-1], [ 0 … n-1]; truy cập thành 
phần A[i], [ j] ta sẽ biết i và j là tương đương hay không. Tuy nhiên, thông 
thường chúng ta chỉ biết trước môt tập nào đó các cặp tương đương (i, j). 
Chúng ta cần đưa ra câu trả lời nhanh cho câu hỏi: với cặp phần tử mới (a, 
b), chúng có tương đương hay không? 
Từ các cặp tương đương (i, j) đã cho, chúng ta sẽ tạo ra các lớp tương 
đương. Điều này được tiến hành như sau. Ban đầu mỗi phần tử của tập S là 
một lớp tương đương chỉ chứa một phần tử. Với mỗi cặp tương đương (i, j), 
ta sử dụng các phép tìm Find(i) và Find(j). Nếu chúng trả về các đại biểu x 
và y khác nhau, thì ta sử dụng phép hợp Union(x, y) để kết hợp hai lớp 
tương đương [x] và [y] thành một lớp mới và huỷ bỏ hai lớp đó. Còn nếu 
Find(i) và Find(j) trả về cùng một đại biểu thì có nghĩa là i và j đã thuộc 
cùng một lớp tương đương, và ta không cần phải làm gì với cặp (i, j) này. 
Sau khi đã tạo ra các lớp tương đương từ các cặp tương đưong (i, j) đã cho, 
để có câu trả lời cho cặp (a, b) được hỏi, chúng ta chỉ cần sử dụng các phép 
tìm Find(a) và Find(b). 
 364
13.4.2 Tạo ra mê lộ 
Hình 13.5 biểu diễn một mê lộ 5 x 6. Chúng ta quan niệm một mê lộ 
như một lâu đài hình chữ nhật gồm m x m phòng, mỗi phòng hoặc là có cửa 
thông sang phòng bên cạnh, hoặc là bị ngăn cách với phòng bên cạnh bởi 
bức tường (mỗi phòng kề với 4 phòng lân cận, trừ các phòng ở cạnh tường 
bao ngoài có số phòng kề ít hơn). Lâu đài có một cửa vào ở phòng góc trên 
bên trái và một lối ra ở phòng góc dưới bên phải (xem hình 13.5). Từ một 
phòng bất kỳ ta có thể đi tới một phòng bất kỳ khác trong lâu đài. Mê lộ cần 
được thiết kế sao cho người đi vào lâu đài tìm được lối ra khỏi lâu đài là hết 
sức khó khăn. 
Hình 13.5. Một mê lộ 
Sau đây chúng ta sẽ trình bày một thuật toán thiết kế mê lộ. Chúng ta 
đánh số các phòng từ 0 đến p. Ban đầu tất cả các phòng đều ngăn cách bởi 
bức tường với các phòng kề như trong hình 13.6. Điều này có nghĩa là ban 
đầu ta xem mỗi phòng ở trong một tập con riêng biệt. Tới một lúc nào đó, 
mỗi một tập con sẽ gồm tất cả các phòng liên thông với nhau, tức là từ một 
phòng bất kỳ trong tập ta có thể đi tới phòng bất kỳ khác trong tập. Tại mỗi 
bước chúng ta sẽ chọn ngẫu nhiên một bức tường ngăn cách 2 phòng a và b. 
Sử dụng phép tìm, nếu Find(a) = x, Find(b) = y và x ≠ y, thì điều đó có nghĩa 
là a và b không liên thông với nhau, và ta phá bức tường để cửa cho 2 phòng 
a và b thông với nhau. Điều này được thực hiện bằng cách sử dụng phép hợp 
Union(x, y) để hợp nhất tập con chứa a với tập con chứa b. Còn nếu a và b 
đã liên thông với nhau, tức Find(a) = Find(b), thì ta để nguyên bức tường đó. 
Lặp lại quá trình trên cho tới khi tất cả các phòng là liên thông với nhau. 
 365
 0 
 6 
 12 
 18 
 24 25 26 27 28 29 
Hình 13.6. Khởi tạo mỗi phòng ở trong một tập con riêng 
(mỗi phòng không có cửa thông sang phòng bên cạnh) 
Để thấy được thuật toán trên làm việc như thế nào, giả sử tới một giai 
đoạn nào đó chúng ta có trạng thái của các phòng như trong hình 13.7. Ở 
tình huống này, chúng ta có họ các tập các phòng liên thông với nhau như 
sau: {0, 1}, {2, 3, 4, 5, 8, 9, 10, 15, 16, 17}, {6}, {7, 12, 13, 18, 24}, {11}, 
{14, 19, 20, 25, 26}, {21, 27}, {22, 23, 28, 29}. Giả sử đại biểu của một tập 
con là phòng có số hiệu nhỏ nhất. Bây giờ chúng ta chọn ngẫu nhiên một 
bức chưa đặt cửa, chẳng hạn đó là bức tường ngăn cách phòng 9 và phòng 
15. Chúng ta thấy rằng phòng 9 và phòng 15 đã liên thông với nhau, bởi vì 
Find(9) = Find(12) = 2, tức là chúng ở trong cùng một tập, và do đó ta để 
nguyên bức tường này. Chọn ngẫu nhiên một bức tường khác, chẳng hạn 
bức tường ngăn cách phòng 18 và phòng 19. Phép tìm Find(18) cho ta đại 
biểu của tập con chứa 18 là 7, phép tìm Find(19) cho ta đại biểu của tập con 
chứa 19 là 14, như vậy 18 và 19 thuộc các tập con khác nhau, và điều này có 
nghĩa là chúng không liên thông với nhau. Do đó ta cần đục cửa ở bức tường 
ngăn cách phòng 18 và 19. Sử dụng phép hợp để hợp nhất tập con chứa 18 
và tập con chứa 19 thành một tập con. 
 1 2 3 4 5 
 7 8 9 10 11 
13 14 15 16 17 
19 20 21 22 23 
 366
 0 1 2 3 4 5 
 6 7 8 9 10 11 
 12 13 14 15 16 17 
 18 19 20 21 22 23 
 24 25 26 27 28 29 
Hình 13.6. Một tình huống trong quá trình thực hiện 
 thuật toán xây dựng mê lộ