CoE KKU

การทำงานของ union/find algorithm ที่ได้กล่าวมาแล้วในกรณีโดยทั่วไปเป็นที่ยอมรับได้เนื่องจากไม่ซับซ้อนและใช้เวลาเฉลี่ยเป็น linear สำหรับลำดับการทำงาน M คำสั่งต่อเนื่องกัน อย่างไรก็ตามมันอาจเกิดกรณี worst case ที่มี running time เป็น O(M log N) ได้ง่ายเป็นเรื่องปกติ เช่น ถ้าเราจัดให้เซตทั้งหมดเข้าไปอยู่ในคิว ๆ หนึ่งและให้ดำเนินการซ้ำ ๆ ด้วยการ dequeue สองเซตแรกและตามด้วย enqueue ผลที่ได้ของการ union เช่นนี้ก็จะเกิดกรณี worst-case ขึ้น ถ้าหากว่ามีการทำงาน find เป็นจำนวนครั้งที่มากกว่าการทำงานของ union มากก็จะทำให้ running time เลวร้ายลงไปกว่า quick-find algorithm ยิ่งไปกว่านั้นจากการสังเกตยังพบว่าเราไม่สามารถปรับปรุงให้การทำงานของอัลกอริทึมของ union ทำงานได้ดีขึ้นเลย เนื่องจากไม่ว่าจะใช้วิธีใดก็จะยังได้ทรีแบบเดียวกัน ดังนั้นจึงเหลือหนทางการปรับปรุงการทำงานด้วยการปรับปรุงการทำงานของ find โดยไม่ต้องไปจัดการกับโครงสร้างใหม่ทั้งหมด

วิธีการที่จะกล่าวถึงนี้เรียกว่า Path compression การทำงานของ path compression เป็นการทำงานที่เกิดขึ้นในระหว่างการทำงานของ find และเป็นอิสระจากการทำงาน unions ไม่ว่าจะมีกรรมวิธีการทำ union แบบใด ในขณะทำงาน find(x) ผลของ path compression คือทุก ๆ โนดบนเส้นทางจาก x ไปยังรากจะได้รับการปรับเปลี่ยนโนดที่เป็นโนดแม่ (parent) ของมันไปเป็นโนดราก (คือเอาโนดรากของทรีมาเป็นโนดแม่ของมัน) รูปที่ 8.14 แสดงผลของ path compression หลังจาก find(14) ที่เกิดขึ้นกับ worst tree ของรูปที่ 8.12

ผลของ path compression ที่เกิดจากการเคลื่อนย้ายเส้นเชื่อมต่อ 2 เส้น ทำให้โนด 12 และ 13 มีตำแหน่งใกล้กับโนดรากมากขึ้นอีกหนึ่งตำแหน่งและโนด 14 และ 15 ใกล้ขึ้นสองตำแหน่ง ดังนั้นจึงหวังได้ว่าการเข้าถึงโนดเหล่านั้นในอนาคตจะทำได้เร็วขึ้น

รูปที่ 8.15 แสดงโปรแกรม path compression ซึ่งเป็นการแก้ไข find algorithm พื้นฐานเพียงเล็กน้อยเท่านั้น กล่าวคือทำให้ s[x] เท่ากับค่าที่ส่งกลับจาก find ดังนั้นหลังจากที่พบโนดรากของเซต (แบบ recursive) แล้วเส้นเชื่อมต่อของโนดแม่ของ x ก็จะ reference ถึงมัน (โนดรากของเซต) สิ่งนี้เกิดขึ้นในแบบ recursive กับทุกโนดบนเส้นทางไปยังโนดราก นั่นคือเป็นการทำงาน path compression

public int find( int x )
{   if ( s[x] <= 0 )
	    return x;
    else
	    return ( s[x] = find ( s[x] );
}

รูปที่ 8.15 ฟังก์ชัน find ที่ใช้ path compression

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

การทำงานของ path compression สามารถเข้ากันได้ (compatible) อย่างดีกับการทำงาน union-by-size ดังนั้นจึงสามารถใช้งาน routines ทั้ง 2 พร้อม ๆ กันได้ เนื่องจากว่าการทำงานโดยตัวของ union-by-size เองนั้นมีค่าคาดหวังของการทำงานต่อเนื่องกันเป็นจำนวน M ครั้งนั้นเป็น linear time และยังไม่เป็นที่แน่ชัดว่ารอบการทำงานที่เพิ่มขึ้นจากการทำงานของ path compression นั้นจะมีประโยชน์ใดต่อการทำงานในกรณีเฉลี่ย อย่างไรก็ตาม พบว่าการผสมผสานระหว่าง path compression และกฎของ smart-union จะสามารถประกันได้ว่าจะได้เป็นอัลกอริทึมที่มีประสิทธิภาพสำหรับทุก ๆ กรณี

path compression ไม่สามารถเข้ากันได้โดยสมบูรณ์กับ union-by-height เนื่องจากว่า path compression จะไปเปลี่ยนความสูงของทรีได้และยังไม่แน่ชัดว่าจะมีวิธีคำนวณที่มีประสิทธิภาพ ดังนั้นจึงค่าความสูงของทรีที่มีการจัดเก็บนั้นจึงเป็นค่าประมาณการ (estimated) (ซึ่งรู้จักกันในชื่อว่า ranks) ดังนั้นจึงเรียกการทำงานนี้ว่า union-by-rank และโดยทฤษฎีแล้วมันจึงมีประสิทธิภาพเหมือนกันกับ union-by-size ยิ่งกว่านั้นการปรับปรุง heights เกิดขึ้นน้อยกว่าการปรับปรุง sizes นั้น ในหัวข้อถัดไปจะได้แสดงให้เห็นว่าการใช้ path compression ร่วมกับการทำ union ที่ไม่ว่าจะเป็น union ด้วยวิธีใดก็สามารถลด worst-case running time ลงได้อย่างมีนัยสำคัญ