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

thumb|360px|การดำเนินการ ''MakeSet'' สร้างเซตโทนขึ้น 8 เซต
thumb|360px|หลังจากมีการดำเนินการ ''Union'' ไประยะหนึ่ง หลาย ๆ เซตได้ถูกรวมเข้าด้วยกัน
ในวิทยาการคอมพิวเตอร์ **โครงสร้างข้อมูลเซตไม่มีส่วนร่วม** () เป็นโครงสร้างข้อมูลที่ใช้เก็บข้อมูลที่แบ่งเป็นหลาย ๆ เซต โดยที่แต่ละเซตไม่มีส่วนร่วมกันเลย (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*) ทั้งนี้หากไม่มีโครงสร้างข้อมูลที่ดีกว่ารายการโยงก็จะไม่สามารถทำให้เวลาในการดำเนินการเร็วกว่านี้ได้

### วิเคราะห์
สาเหตุที่การใช้ *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 ใน พ.ศ. 2507 โดยที่การวิเคราะห์ประสิทธิภาพของโครงสร้างข้อมูลนี้อย่างละเอียดตามมาหลังจากนั้นหลายปี

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


```text
function MakeSet(x)
    x.parent := x
```



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



```text
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*) สามารถเขียนเป็นรหัสเทียมได้ดังนี้


```text
function MakeSet(x)
    x.parent := x
```



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



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


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


```text
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
* *[http://citeseer.ist.psu.edu/anderson94waitfree.html 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

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