Disjoint Set

สมมุติว่าเรามี Set อยู่ 8 ตัวคือ {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7} เราจะให้แต่ละตัวเป็นต้นไม้ 1 ต้น โดยมี Root เป็นชื่อเซ็ตนั้นดังนี้

ถ้า set 0 จะมี 0 เป็น root และถ้า set 1 จะมี 1 เป็น root

สมมุติว่าถ้า union 4 กับ 5 เข้าด้วยกันจะได้ {4, 5} ดังนี้

สมมุติว่าถ้า union 6 กับ 7 เข้าด้วยกัน จะได้ {6, 7} ดังนี้

และถ้า union 4 กับ 6 เข้าด้วยกันจะได้เป็น ภาพดังนี้

ณ ปัจจุบัน set 4 จะมีสมาชิกอยู่ 4 ตัวคือ {4, 5, 6, 7} แต่ set 6 จะไม่มีสมาชิก เนื่องจาก {6, 7} กลายไปเป็นสมาชิกของ set 4 แล้ว

การอิมพลีเมนต์ในรูปแบบอะเรย์

ถ้าเราจะ implement tree ในลักษณะ array เราจะมี array ขนาด 7 ช่องดังนี้

เริ่มต้นเราจะให้ทุกช่องในอะเรย์มีค่าเป็น -1 ทั้งหมด

ครั้งแรกเมื่อ union 4 กับ 5 จะทำให้ค่าในอะเรย์เปลี่ยนไปดังนี้

สมมุติว่าถ้า union 6 กับ 7 เข้าด้วยกัน จะได้ {6, 7} เนื่องจาก 6 เป็นแม่ของ 7 เราจะเอา 6 ไปเก็บในช่อง 7 ดังนี้

และถ้า union 4 กับ 6 เข้าด้วยกัน 4 จะเป็นแม่ของ 6 ทำให้เราต้องเอา 4 ไปใส่ในช่อง 6 ดังนี้

 Arbitrary Union

วิธีการ union โดยนำไปต่อกับตัวแม่ (ที่เป็นโหนดที่มีค่าน้อยกว่า) แบบนี้เราเรียกว่าเป็น Arbitrary Union แต่จะมีข้อเสียคือต้นไม้จะมีความสูงขึ้นเรื่อยๆ เช่น ในภาพข้างบน ถ้าเราจะ union (3, 4) เข้าด้วยกันจะได้ภาพดังนี้

Smart Union

วิธีการที่ดีกว่าเราเรียกว่า Smart Union ซึ่งมีอยู่ 2 แบบคือ union by size และ union by height โดยมีหลักการคือ

o    union by size ให้ถือว่า tree ที่มี size มากกว่าเป็น root

o    union by height ให้ถือว่า tree ที่มี height สูงกว่า เป็น root

Union by size

ตัวอย่างเช่น ตอนเริ่มต้น

ค่าติดลบ ที่อยู่ในอะเรย์ นอกจากบอกว่าเป็น Root แล้ว ยังบอกให้รู้ว่ามีขนาด (size) เป็น 1 ด้วย โดยไม่คิดเครื่องหมายลบ

เช่น union (4, 5) เนื่องจาก 4 กับ 5 มี size เท่ากัน ดังนั้นจะ union ตามปกติ ได้ภาพดังนี้

จากภาพนี้ ถ้าเรา union (6, 7) เนื่องจาก size เท่ากัน ดังนั้นจะ union ไปตามปกติ ให้ 6 เป็นแม่ และให้ 7 เป็นลูกดังนี้

ถ้าเรา union (4, 6) ทั้ง 4 กับ 6 มี size เท่ากันดังนั้น union ไปตามปกติโดยให้ 4 เป็นแม่ และให้ 6 เป็นลูกดังนี้

ถ้าเรา union (3, 4) เนื่องจาก 3 มี size = 1 แต่ 4 มี size = 4 ดังนั้น ตัวที่มี size มากกว่าต้องเป็นแม่ของตัวน้อย ดังนั้น 4 เป็นแม่ และ 3 เป็นลูกดังนี้

Union by height

สมมุติว่าเรามี set อยู่แบบนี้

สังเกตว่าค่าติดลบ นอกจากจะหมายถึง root แล้วยังเป็นความสูงของต้นไม้ (ต้องลบ 1 ออกก่อน) ด้วย เช่น -3 หมายถึงต้นไม้นี้สูง 2 นั่นเอง

สมมุติว่าเราจะ union (3, 4) ตัวที่มี height มากกว่าจะต้องเป็นแม่ ดังนั้น 4 มี height = 2 ส่วน 3 มี height = 0 ดังนั้น 3 ต้องกลายเป็นลูกของ 4 ดังนี้

จะเห็นว่าทั้งแบบ Union by size และ Union by height จะช่วยลดความสูงของต้นไม้ได้ดีกว่า Arbitrary Union