CoE KKU

การทำงาน find ไม่ต้องการคำตอบที่เป็นการระบุถึงชื่อใด ๆ หากแต่เพียงต้องการคำตอบว่าการ find สมาชิกทั้งสองตัวนั้นจะให้คำตอบที่เหมือนกันถ้า (if and only if) มันอยู่ใน set เดียวกัน แนวคิดหนึ่งคือ การใช้โครงสร้างทรี (tree) สำหรับแต่ละเซต เนื่องจากสมาชิกแต่ละตัวนั้นมีรากเดียวกัน ดังนั้นเราจึงใช้ชื่อของรากเป็นชื่อของเซตดังกล่าวได้ เราจะแทนเซตหนึ่งเซตด้วยทรีหนึ่งทรี ตอนเริ่มต้นแต่ละเซตประกอบด้วยสมาชิกหนึ่งตัว (กลุ่มของทรีเรียกว่า forest) ทรีที่เราใช้นี้ไม่จำเป็นต้องเป็น binary trees และสิ่งที่ต้องการคือการเชื่อมต่อกับโนดแม่ (parent link) เท่านั้น ชื่อของเซตหนึ่งก็คือโนดที่รากของทรี และเนื่องจากเราต้องการเพียงชื่อของ parent เราจึงใช้อะเรย์เป็นที่เก็บทรี กล่าวคือ สำหรับแต่ละ s[i] ในอะเรย์คือ parent ของสมาชิกตัวที่ i ถ้า i เป็นรากก็ใน s[i] = -1 รูปที่ 8.1 แสดง forest ที่ s[i] = -1 เมื่อ 0 ≤ i < 8 ดังเช่นที่แสดงใน binary heap เราจะแสดงโครงสร้างในรูปของทรีทั้ง ๆ ที่ความจริงเราใช้อะเรย์ และเพื่อความสะดวกเราจะใช้เส้นในแนวตั้งแทนเส้นเชื่อมจากราก (parent link) ไปยังโนดแม่ของมัน

เราสามารถทำ union ของเซตสองเซตได้ด้วยการควบรวมทรี 2 ตัวเข้าด้วยการด้วยการใช้ parent link ของรากของทรีหนึ่ง เชื่อมเข้ากับโนดรากของอีกทรีหนึ่งซึ่งใช้เวลาเป็นเวลาคงที่ รูปที่ 8.2, 8.3, และ 8.4 เป็น forest หลังการทำ union(4,5), union(6,7), union(4,6) โดยที่หลังทำ union(x,y) แล้วมีรากเป็น x รูปที่ 8.5 แสดงผลของ forest ที่ได้

รูปที่ 8.5 อะเรย์ของสมาชิกในทรีข้างบน

การทำงาน find(x) เพื่อหาสมาชิก x จะได้ผลเป็นรากของทรีที่มี x เวลาที่ใช้ขึ้นอยู่กับความลึกของโนดที่เป็น x โดยที่ถ้าเราสามารถหาโนด x ได้ด้วยเวลาคงที่ ด้วยวิธีการดังกล่าวนี้ เราอาจต้องสร้างทรีที่มีความลึก N – 1 ดังนั้น worst-case running time ของ find จึงเป็น O(N) กรณีทั่วไป running time ของการทำงาน M ครั้งต่อเนื่องกันก็จะมี worst-case running time เป็น O(MN) โปรแกรมในรูปที่ 8.6 ถึงรูปที่ 8.9 แสดงอัลกอริทึมพื้นฐานโดยสมมติให้มีการทำงาน error check มาก่อนแล้ว ในโปรแกรมการทำงาน union เกิดขึ้นที่รากของทรี ในบางครั้งการทำงานเกิดขึ้นด้วยการส่งผ่านพารามิเตอร์เป็นสมาชิก 2 ตัว และการทำงาน union มีการทำงาน find 2 ครั้งเพื่อหาตัวโนดราก

/* Disjoint set class. 
 * Does not use union heuristics or path compression.
 * Elements in the set are numbered starting at 0. */
public class DisjSets 
{   public DisjSets( int numElements ) { /* Figure 8.7 */ }
    public void union( int root1, int root2 )    
	{/* Figure 8.8 and Figure 8.13 */ }
    public int find( int x ) {/* Figure 8.9 and Figure 8.15*/ }
    private int [ ] s;
}

รูปที่ 8.6 โครงร่างของคลาส Disjoint set

public DisjSets( int numElements )
{
    s = new int [ numElements ];
    for( int i = 0; i < s.length; i++ )
        s[ i ] = -1;
}

รูปที่ 8.7 Initialization routine ของ Disjoint set

/* Union two disjoint sets.
 * For simplicity, we assume root1 and root2 are distinct
 * and represent set names.*/
public void union( int root1, int root2 )
{
    s[ root2 ] = root1;
}

รูปที่ 8.8 union

/* Perform a find. Error checks omitted for simplicity. */
public int find( int x )
{
    if( s[ x ] < 0 )
        return x;
    else
        return find( s[ x ] );
}

รูปที่ 8.9 อัลกอริทึมอย่างง่ายของ find

การวิเคราะห์กรณีเฉลี่ยขึ้นอยู่กับว่าจะกำหนดนิยามของคำว่าเฉลี่ยอย่างไรเมื่อพิจารณาถึง union ดังนั้นจึงมีความยุ่งยากมากและมีผู้เสนอโมเดลการวิเคราะห์หลายโมเดลมาก ถึงกระนั้นก็ยังไม่เป็นข้อยุติเป็นการทั่วไปได้ มีผู้เสนอ running time สำหรับกรณีเฉลี่ยเป็น $\Theta(M)$, $\Theta(M\ log\ N)$, และ $\Theta(MN)$ ขึ้นอยู่กับโมเดลที่ใช้ที่แตกต่างกัน