โครงสร้างข้อมูลเซตไม่มีส่วนร่วม

ในวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูลเซตไม่มีส่วนร่วม () เป็นโครงสร้างข้อมูลที่ใช้เก็บข้อมูลที่แบ่งเป็นหลาย ๆ เซต โดยที่แต่ละเซตไม่มีส่วนร่วมกันเลย (disjoint, nonoverlapping) โดยมีขั้นตอนวิธียูเนียนและค้นหา () เป็นขั้นตอนวิธีที่ดำเนินการบนโครงสร้างข้อมูลนี้ มีจุดประสงค์คือ 1. ต้องการทดสอบว่าสมาชิกสองตัวที่กำหนดให้อยู่ในเซตเดียวกันหรือไม่ 2. ต้องการรวมเซตสองเซตเข้าด้วยกันเป็นเซตใหญ่เพียงเซตเดียว

เพื่อที่ดำเนินการตามจุดประสงค์ จึงมีฟังก์ชันในการดำเนินการ 2 อย่างคือ
 ค้นหา (Find) : จุดประสงค์เบื้องต้นเป็นการหาว่าสมาชิกที่ต้องการจะทดสอบอยู่ในเซตชื่ออะไร เพื่อที่จะได้นำมาตอบคำถามว่าสมาชิกสองตัวที่ต้องการจะทดสอบนั้นอยู่ในเซตเดียวกันหรือไม่ เนื่องจากจุดประสงค์ไม่ได้ต้องการชื่อเซตจริง ๆ ในการดำเนินการจึงอาจจะไม่ได้กำหนดชื่อของเซตจริง ๆ แต่ใช้วิธีการบางอย่างเพื่อให้ประมวลผลข้อมูลได้ง่าย
 ยูเนียน (Union) : เป็นการรวมสองเซตที่กำหนดให้เข้าด้วยกันเป็นเพียงเซตเดียว

เนื่องจากโครงสร้างข้อมูลเซตไม่มีส่วนร่วมส่วนใหญ่จะดำเนินการด้วยขั้นตอน วิธียูเนียนและค้นหา จึงทำให้มีการเรียกโครงสร้างข้อมูลนี้ว่า โครงสร้างข้อมูลยูเนียนและค้นหา นอกจากนี้ อาจนิยามการดำเนินการ สร้างเซต (MakeSet) ซึ่งจะสร้างเซตตั้งต้นขึ้น โดยเซตตั้งต้นจะมีสมาชิกเพียงแค่ตัวเดียวเท่านั้น (เซตโทน) เมื่อใช้ 3 การดำเนินการนี้ร่วมกันจะสามารถแก้ไขปัญหาการแบ่งบางอย่างได้ (ดูที่หัวข้อการนำไปใช้งาน)

ตามที่ได้เกริ่นมาแล้วว่าจุดประสงค์ของการดำเนินการ ค้นหา อันที่จริงแล้วคือการทดสอบว่าสมาชิกสองตัวที่จะทดสอบนั้นอยู่ในเซตเดียวกันหรือไม่ ชื่อเซตจึงไม่สำคัญ เพื่อให้ประมวลผลข้อมูลได้ง่ายจึงมีการใช้ชื่อของสมาชิกตัวหนึ่งในเซตนั้นมาเป็นชื่อเล่นของเซต กล่าวคือให้สมาชิกตัวนั้นมาเป็นตัวแทนของทั้งเซตไปเลย

 รายการโยงเซตไม่มีส่วนร่วม 
วิธีการสร้างโครงสร้างข้อมูลเซตไม่มีส่วนร่วมแบบง่ายที่สุดก็คือสำหรับแต่ละเซตให้สร้างรายการโยงขึ้นมา และให้สมาชิกตัวด้านหน้าสุดของรายการโยงเป็นตัวแทนของเซตนั้น

การสร้างเซต ก็คือการสร้างรายการโยงความยาว 1 ขึ้นเป็นจำนวนที่ต้องการ การยูเนียน ก็จะเป็นการนำรายการโยงสองรายการมาต่อกันในเวลาคงที่ ข้อเสียของการอิมพลีเมนต์แบบนี้คือในการค้นหาแต่ละครั้งจะต้องใช้เวลา Ω(n) จากการไล่จากสมาชิกตัวปัจจุบันไปยังสมาชิกตัวหน้าสุดเพื่อหาชื่อเซต

วิธีที่จะทำให้การดำเนินการค้นหาไม่ต้องเสียเวลาไล่ในรายการโยงถึง Ω(n) ก็คือสำหรับทุก ๆ สมาชิกในรายการโยง ให้มีตัวชี้โยงมายังสมาชิกตัวแรกสุดของรายการโยง ซึ่งจะทำให้การดำเนินการค้นหา ใช้เวลาเพียงแค่ O(1) เท่านั้น แต่ข้อเสียของวิธีนี้ก็คือในการยูเนียน จะต้องมาไล่ปรับปรุงตัวชี้ของสมาชิกทั้งหลายใหม่ให้ถูกต้องด้วย ทำให้การยูเนียน เสียเวลา Ω(n) แทน

สำหรับวิธีที่ใช้ตัวชี้มาช่วยนั้น หากมีการเก็บความยาวของรายการโยงไว้ในทุกขณะด้วย จะสามารถเพิ่มความเร็วในการดำเนินการได้โดยใช้ฮิวริสติก weighted-union heuristic ซึ่งมีหลักการว่าแทนที่การยูเนียนจะนำรายการโยงทั้ง 2 มาต่อกันตรง ๆ ให้ตรวจสอบก่อนว่ารายการโยงใดสั้นกว่า แล้วจึงนำรายการโยงที่สั้นไปต่อหลังจากรายการโยงที่ยาว ซึ่งหากทำตามขั้นตอนดังกล่าวจะทำให้การดำเนินการสร้างเซต ค้นหา และยูเนียน รวม m ครั้ง บนโครงสร้างข้อมูลเซตไม่มีส่วนร่วมที่มีสมาชิกทั้งหมด n ตัว ใช้เวลา O(m + n log n)Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498-524. ทั้งนี้หากไม่มีโครงสร้างข้อมูลที่ดีกว่ารายการโยงก็จะไม่สามารถทำให้เวลาในการดำเนินการเร็วกว่านี้ได้

 วิเคราะห์ 
สาเหตุที่การใช้ weighted-union heuristic ทำให้เวลาการดำเนินการทั้งหลายใช้เวลา O(m + n log n) มาจากเหตุผลที่ว่าการรวมรายการโยงขนาดสั้น ๆ เข้ากับรายการโยงขนาดยาว ๆ จะเสียเวลาเปลี่ยนตัวชี้ของรายการโยงขนาดสั้นเท่านั้น ดังนั้นกรณีเลวร้ายที่สุดก็จะเกิดจากการที่นำรายการโยงขนาดพอ ๆ กันมาต่อกันเสมอ ซึ่งจะทำให้การต่อแต่ละครั้งเสียเวลา O(n) แต่การที่นำมาต่อกันเช่นนี้ก็ทำให้เซตถูกยูเนียนเข้าด้วยกันอย่างรวดเร็ว ซึ่งโครงสร้างเซตไม่มีส่วนร่วมขนาด n จะมีการ ยูเนียน อย่างเลวร้ายได้มากสุดเพียง log n ครั้งเท่านั้น จึงทำให้เฉพาะการยูเนียนในกรณีเลวร้ายที่สุดเสียเวลา O(n log n)

ในการดำเนินการค้นหา ก็สามารถใช้ตัวชี้เพื่อไปยังสมาชิกตัวด้านหน้าสุดของรายการโยงได้ภายในเวลา O(1) ตามที่กล่าวมาแล้ว

แนวคิดในการนำเซตที่มีขนาดเล็กกว่าไปต่อเซตที่มีขนาดใหญ่กว่ายังปรากฏให้เห็นในโครงสร้างข้อมูลอื่น ๆ เช่นฮีปทวิภาค หรือฮีปฟีโบนัชชีอีกด้วย

 ป่าไม้เซตไม่มีส่วนร่วม 
ป่าไม้เซตไม่มีส่วนร่วมเป็นโครงสร้างข้อมูลซึ่งจะใช้โครงสร้างข้อมูลต้นไม้ในการแทนแต่ละเซต และโครงสร้างข้อมูลต้นไม้นี้ก็จะจัดเก็บโดยใช้รูปแบบ Spaghetti stack กล่าวคือแต่ละจุดยอดจะโยงไปยังพ่อของตัวมัน ป่าไม้เซตไม่มีส่วนร่วมได้มีการคิดค้นโดย 
Bernard A. Galler และ Michael J. Fischer ใน พ.ศ. 2507Bernard A. Galler and Michael J. Fischer. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), pp. 301–303. The paper originating disjoint-set forests. ACM Digital Library โดยที่การวิเคราะห์ประสิทธิภาพของโครงสร้างข้อมูลนี้อย่างละเอียดตามมาหลังจากนั้นหลายปี

ในป่าไม้เซตไม่มีส่วนร่วมจะกำหนดให้ตัวแทนของแต่ละเซตคือจุดยอดที่เป็นรากของต้นไม้ ดังนั้นการดำเนินการค้นหา ก็คือการกระโดดสูงขึ้นไปเรื่อย ๆ จนกว่าจะเจอราก ส่วนการยูเนียนก็คือการดำเนินการค้นหากับต้นไม้ทั้งสองต้นเพื่อหารากของต้นไม้ทั้งสอง และนำรากของต้นไม้หนึ่งไปต่อกับรากของต้นไม้อีกต้น อาจเขียนเป็นรหัสเทียมออกมาได้ดังนี้

function MakeSet(x)
    x.parent := x

function Find(x)
    if x.parent == x
       return x
    else
       return Find(x.parent)

function Union(x, y)
    xRoot := Find(x)
    yRoot := Find(y)
    xRoot.parent := yRoot

อย่างไรก็ตาม ประสิทธิภาพของป่าไม้เซตไม่มีส่วนร่วมข้างต้นแย่กว่าการใช้รายการโยงเซตไม่มีส่วนร่วมแบบอย่างง่ายเสียอีก เพราะต้นไม้ที่เกิดขึ้นอาจจะไม่สมดุลเป็นอย่างมาก ในกรณีเลวร้ายมากที่สุดอาจถึงขั้นกลายเป็นเส้นตรงเลย ซึ่งจะทำให้การดำเนินการทั้งค้นหาและยูเนียน แต่ละครั้งใช้เวลา O(n) อย่างไรก็ตามขั้นตอนวิธีนี้สามารถเพิ่มประสิทธิภาพได้ 3 วิธี

วิธีแรก เรียกว่า union by height ใช้แนวคิดว่าให้นำต้นไม้ที่มีความสูงต่ำกว่าไปต่อต้นไม้ที่มีความสูงมากกว่าเสมอเหมือนแนวคิดของ weighted-union heuristic ด้วยวิธีนี้จะทำให้ต้นไม้มีความสูงเพิ่มขึ้นก็ต่อเมื่อนำต้นไม้ที่มีความสูงเท่ากันพอดีมายูเนียนกัน และความสูงจะเพิ่มเพียงแค่ 1 ด้วย ดังนั้นเนื่องจากสามารถมีการยูเนียนได้เพียง log n ครั้ง ความสูงของต้นไม้จึงเป็น log n ด้วย ส่งผลให้การดำเนินการทั้งค้นหา และยูเนียน ในแต่ละครั้งใช้เวลา O(log n) สามารถเขียนเป็นรหัสเทียมได้ดังนี้

function MakeSet(x)
    x.parent := x

function Find(x)
    if x.parent == x
        return x
    else
        return Find(x.parent)

function Union(x, y)
    xRoot := Find(x)
    yRoot := Find(y)
    xRoot.parent := yRoot

วิธีที่สองเรียกว่า การอัดวิถี โดยเป็นการที่พยายามทำให้โครงสร้างต้นไม้แบนราบเมื่อมีการดำเนินการค้นหา แนวคิดมาจากการที่การดำเนินการค้นหาแต่ละครั้งต้องวิ่งไล่ในวิถีผ่านจุดยอดต่าง ๆ จนถึงจุดยอดรากอยู่แล้ว ดังนั้นเมื่อทราบแล้วว่าจุดยอดรากคืออะไร ก็จะเปลี่ยนให้แต่ละจุดยอดบนวิถีดังกล่าวมีพ่อเป็นจุดยอดรากโดยตรงเลย ซึ่งเป็นการเพิ่มความเร็วในการดำเนินการค้นหาในครั้งถัด ๆ มา อย่างเห็นได้ชัด การเปลี่ยนความสัมพันธ์เช่นนี้ไม่ทำให้เกิดปัญหาใด ๆ ทั้งสิ้นเนื่องจากในการเปลี่ยนแปลงนี้ไม่ได้ทำให้จุดยอดรากเปลี่ยนไป ทำให้ตัวแทนเซตยังเหมือนเดิม และจุดยอดในต้นไม้ดังกล่าวก็ยังคงอยู่ในต้นไม้ต้นเดิมหลังเปลี่ยนแปลงโครงสร้างแล้ว ดังนั้นการเปลี่ยนแปลงโครงสร้างจึงทำให้เซตที่แทนออกมามีลักษณะเหมือนก่อนการเปลี่ยนแปลงทุกประการ ตัวอย่างรหัสเทียมของฟังก์ชัน find ที่ใช้ในการดำเนินการค้นหาคือ

function Find(x)
    if x.parent != x
        x.parent := Find(x.parent)
    return x.parent

 การนำไปใช้งาน 

 ประวัติ 

 อ้างอิง 

 แหล่งข้อมูลอื่น 
 C++ implementation , part of the Boost C++ libraries
 A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
 Java applet: A Graphical Union-Find Implementation, by Rory L. P. McGuire
 Wait-free Parallel Algorithms for the Union-Find Problem , a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union-Find that never needs to block
 Python implementation

หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:โครงสร้างข้อมูล