CoE KKU

การ unions ดังที่กล่าวมาข้างบนไม่มีข้อกำหนดใดกำกับเพียงแต่ใช้ทรีตัวที่สองไปเป็นทรีย่อยของทรีตัวแรก การปรับปรุงอย่างง่ายให้การทำงานดีขึ้นคือกำหนดให้ทรีที่มีขนาดเล็กกว่าไปเป็นทรีย่อยของทรีที่มีขนาดใหญ่กว่าเสมอ และเรียกวิธีนี้ว่า union-by-size

การ union กันทั้งสามในตัวอย่างที่ผ่านมามีขนาดเท่ากันทั้งหมดจึงกล่าวได้ว่ามันเป็น union-by-size เช่นกัน และถ้าการดำเนินการต่อไปเป็นการทำ union (3,4) ก็จะได้ forest ดังรูปที่ 8.10 และในกรณีที่เราไม่คำนึงถึงขนาดของทรีเราก็จะได้ forest ที่มีขนาดลึกมากกว่าดังรูปที่ 8.11

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

การใช้วิธีดังกล่าวนี้จะต้องบันทึกขนาดของแต่ละทรีในระหว่างทำงานด้วย เนื่องจากเราใช้อะเรย์ ดังนั้นเราจึงสามารถใส่ค่าติดลบ (negative) ให้แก่รากของทรีลงในรายการของอะเรย์ โดยเริ่มต้นจะให้มีค่าเป็น –1 ทั้งหมด เมื่อมีการทำ union ก็จะทำการตรวจสอบขนาด และขนาดใหม่ก็คือผลบวกของขนาดเดิม ดังนั้นโปรแกรมจึงไม่ได้ยุ่งยากแต่อย่างใด การทำงานต่อเนื่องกัน M ครั้ง โดยเฉลี่ยแล้วใช้เวลาเป็น $O(M)$ ถ้าใช้ union-by-size เนื่องจากการ unions ที่เป็นแบบสุ่มนั้นโดยทั่วไปแล้วเป็นการควบรวมเซตที่มีขนาดเล็กมาก (ปกติมีสมาชิกตัวเดียว) เข้ากับเซตที่มีขนาดใหญ่ตลอดการทำงานของอัลกอริทึม

อีกวิธีการหนึ่งที่ประกันได้เช่นกันว่าทรีทั้งหมดมีความลึกมากสุดเป็น $O(log\ N)$ คือ วิธี union-by-height วิธีการนี้จะทำการ unions ด้วยการใช้ทรีที่มีความลึกน้อยกว่าไปเป็นทรีย่อยของทรีที่มีความลึกมากกว่า ด้วยวิธีนี้จะทำให้ความสูงของทรีเพิ่มขึ้นได้ก็ต่อเมื่อทรีที่นำมาควบรวมกันนั้นมีความลึกเท่ากันเท่านั้น และจะทำให้มีความสูงของทรีเพิ่มขึ้นหนึ่งระดับ รูปข้างล่างนี้แสดงรูปทรีและโครงสร้างที่ใช้งานจริงของ union-by-size และ union-by-height และรูปที่ 8.13 เป็นโปรแกรม union-by-height

union-by-size

union-by-height

public void union ( int  root1, int  root2 )
{
    if ( s[root2] < s[root1] )  	/* root2 is deeper */
	    s[root1] = root2;     	/* make root2 new root */
    else
    {
	    if ( s[root1] == s[root2] )
	       s[root1]--; 		    /* update height if same */
 	    s[root2] = root1; 		/* make root1 new root */
    }
}

รูปที่ 8.13 ฟังก์ชัน union-by-height (rank)