Cây biểu diễn tập hợp
Một trong các ứng dụng của cây là dùng cây để biểu diễn các tập hợp rời nhau. Khi đó có thể thực hiện phép hợp các tập hợp rời nhau. Để dùng cây biểu diễn tập, ta chọn một phần tử trong tập hợp làm ...
Một trong các ứng dụng của cây là dùng cây để biểu diễn các tập hợp rời nhau. Khi đó có thể thực hiện phép hợp các tập hợp rời nhau.
Để dùng cây biểu diễn tập, ta chọn một phần tử trong tập hợp làm đại diện cho tập. Phần tử này sẽ làm gốc của cây. Các phần tử khác trong tập và các nút của cây. Trong hình vẽ bên có biểu diễn cây của hai tập: một tập hợp gồm các phần tử A, B, C, D, một tập hợp gồm các phần tử E,F. Để lưu trữ cầu trúc cây này, mỗi phần tử được gán thêm một trương parent chỉ tới nút cha của chúng. Trong hình vẽ ta có Parent(D)= B, Parent(C)= A, Parent(E)= F. Vì nút gốc u không có Parent nên người ta cũng tận dụng trường parenr(u) của nút gốc u để ghi số phần tử của tập mà nó đại diện. Chẳng hạn trong hình bên Parent(A)= -4, Parent(E) = -2. Khi ấy cũng có thể trường parent của các nút không là gốc nhận gia trị là chỉ số (index) của nút cha. Chẳng hạn nếu trong hình bên chỉ số của các nút A, B, C, D, E, F tương ứng là các số nguyên dương 1, 2, 3, 4, 5, 6 thì Parent(D)= 2,Parent(C)= 1,Parent(B)= 1,Parent(A)= -4, Parent(F)= 5, Parent(E)=-2.
Tạo một tập mới chỉ gồm một phần tử u
Khi đó cây biểu diễn tập chỉ có một nút gốc.
Create_set(u);
Parent(u)= -1
Tìm tập hợp chứa phần tử u
Đấy chính là tìm phần tử đại diện của tập, hay tìm nút gốc của cây
Find_set(u);
v:= u;
While Parent(v)> 0 do v:= Parent(v)
Return v
Hợp hai tập
Hợp hai tập hợp rời nhau chứa hai phần tử u, v là hợp hai cây thành một cây, bằng cách chọn một trong hai gốc làm gốc của tập mới, còn gốc của cây kia thành con của gốc ấy. Để có thể rút ngắn thời gian tìm kiếm ta chọn gốc của cây chứa nhiều phần tử hơn làm gốc của cây mới. Chẳng hạn trong hình vẽ trên, khi hợp hai tập {A, B, C, B, D} và {E, F} ta gán Parent(E):= 1, Parent (A) = -5.
Union_set(u,v);
x:=Find_set(u);
y:=Find_set(v);
if Parent(x)>Parent(y) then
Parent(y):= Parent(y)+Parent(x);
Parent(x):= Index(y);
else
Parent(x):= Parent(y)+Parent(x);
Parent(y):= Index(x);
