Cấu trúc dữ liệu cho các tập hợp không giao nhau

Trong khoa học máy tính, cấu trúc dữ liệu cho các tập hợp không giao nhau là một cấu trúc dữ liệu để lưu trữ một tập hợp các phần tử được phân chia thành nhiều tập hợp con không giao nhau. Thuật toán hợp-tìm là một thuật toán cho phép thực hiện hai thao tác sau:

Tìm: Tìm xem một phần tử cho trước nằm trong tập hợp nào. Có thể dùng để xác định hai phần tử cho trước có nằm trong cùng một tập hợp hay không.
Hợp: Hợp hai tập hợp làm một.

Do nó hỗ trợ hai thao tác trên nên cấu trúc dữ liệu cho các tập hợp không giao nhau còn được gọi là cấu trúc dữ liệu hợp tìm. Một thao tác quan trọng nữa nhưng thường rất đơn giản là Tạo-tập, dùng để tạo một tập mới chỉ chứa đúng một phần tử.

Để định nghĩa các thao tác trên một cách cụ thể, cần có một cách để ghi nhớ các tập. Một phương pháp phổ biến là dùng một phần tử cố định của mỗi tập để đại diện cho tập đó. Tìm(x) trả về phần tử đại diện của tập chứa x. Hợp nhận hai đối số là phần tử đại diện của hai tập.

Rừng các tập không giao nhau sửa

Rừng các tập không giao nhau là cấu trúc dữ liệu trong đó mỗi tập được biểu diễn bởi một cây, trong đó mỗi nút lưu một con trỏ đến nút cha của nó. Cấu trúc dữ liệu này được mô tả lần đầu tiên bởi Bernard A. Galler và Michael J.Fischer năm 1964,^[1] nhưng độ phức tạp tính toán của nó chỉ được phân tích chính xác nhiều năm sau đó.

Trong rừng các tập không giao nhau, đại diện của mỗi tập là nút gốc của cây biểu diễn tập đó. Thao tác tìm đi theo các con trỏ đến nút cha cho tới khi đến nút gốc. Thao tác hợp hợp hai cây làm một bằng cách gắn một nút gốc vào làm nút con của nút gốc kia. Một phương pháp cài đặt các thao tác này là như sau:

function Tạo-tập(x)
x.cha ← x

function Tìm(x)
if x.cha == x then
return x
else
return Tìm(x.cha)

function Hợp(x, y)
xGốc ← Tìm(x)
yGốc ← Tìm(y)
xGốc.cha ← yGốc

Theo như cách cài đặt đơn giản như trên thì phương pháp này kém hiệu quả do các cây không cân bằng. Có hai cách để làm thuật toán hiệu quả hơn.

Phương pháp thứ nhất, gọi là hợp dùng hạng, là luôn gắn nút gốc cây nhỏ hơn vào làm nút con của nút gốc cây lớn hơn. Cụ thể hơn, mỗi cây đều có một tham số, gọi là hạng. Cây có đúng một phần tử có hạng bằng 0. Khi hợp hai cây cùng có hạng r, hạng của cây mới sẽ là r+1. Chỉ với phương pháp này, cấu trúc dữ liệu đã đảm bảo thời gian trừ dần $O(\log n)$ cho mỗi thao tác. Sau đây là mã giả mới của Tạo-tập và Hợp cho thuật toán cải tiến.

function Tạo-tập(x)
x.cha ← x
x.hạng ← 0

function Hợp(x, y)
xGốc ← Tìm(x)
yGốc ← Tìm(y)
if xGốc == yGốc then
return
if xGốc.hạng < yGốc.hạng then
xGốc.cha ← yGốc
else if xGốc.hạng > yGốc.hạng then
yGốc.cha ← xGốc
else
yGốc.cha ← xGốc
xGốc.hạng ← xGốc.hạng + 1

Cải tiến thứ hai, gọi là nén đường, là một cách để rút ngắn đường trên cây khi thực hiện thao tác tìm. Ý tưởng của cải tiến này là bất cứ nút nào được thăm trong một thao tác tìm đều được gắn trực tiếp với nút gốc, để các thao tác tìm sau này nếu lại đi qua các nút này thì không cần phải lặp lại các thao tác đã thực hiện. Sau đây là mã giả mới cho thao tác Tìm.

function Tìm(x)
if x.cha == x then
return x
else
x.cha ← Tìm(x.cha)
return x.cha

Hai cải tiến này bổ trợ cho nhau. Khi sử dụng cả hai, thời gian trừ dần của mỗi thao tác là $O(\alpha (n))$ ,^[2] trong đó $\alpha (n)$ là hàm ngược của $f(n)=A(n,n)$ , với $A(n,n)$ là hàm Ackermann tăng rất nhanh. Với hầu như tất cả các giá trị thực tế của n, gia trị của $\alpha (n)$ là nhỏ hơn 5.

Độ phức tạp tính toán trên là tối ưu: Fredman và Saks năm 1989 đã chứng minh một thuật toán hợp tìm bất kì đều cần đọc trung bình $\Omega (\alpha (n))$ ô nhớ cho mỗi thao tác.^[3]

Ghi chú sửa

^ Bernard A. Galler, Michael J. Fischer (1964), “An improved equivalence algorithm”, Communications of the ACM, 7, tr. 301–303
^ Tarjan, Robert Endre (1975). “Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884.
^ M. Fredman,M. Saks (1989), “The cell probe complexity of dynamic data structures”, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, tr. 345–354"Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets."

[1] Bernard A. Galler, Michael J. Fischer (1964), “An improved equivalence algorithm”, Communications of the ACM, 7, tr. 301–303

[2] Tarjan, Robert Endre (1975). “Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884.

[3] M. Fredman,M. Saks (1989), “The cell probe complexity of dynamic data structures”, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, tr. 345–354"Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets."

[1]

[2]

[3]