เมนูนำทาง
โครงสร้างข้อมูลเซตไม่มีส่วนร่วม รายการโยงเซตไม่มีส่วนร่วมวิธีการสร้างโครงสร้างข้อมูลเซตไม่มีส่วนร่วมแบบง่ายที่สุดก็คือสำหรับแต่ละเซตให้สร้างรายการโยงขึ้นมา และให้สมาชิกตัวด้านหน้าสุดของรายการโยงเป็นตัวแทนของเซตนั้น
การสร้างเซต ก็คือการสร้างรายการโยงความยาว 1 ขึ้นเป็นจำนวนที่ต้องการ การยูเนียน ก็จะเป็นการนำรายการโยงสองรายการมาต่อกันในเวลาคงที่ ข้อเสียของการอิมพลีเมนต์แบบนี้คือในการค้นหาแต่ละครั้งจะต้องใช้เวลา Ω(n) จากการไล่จากสมาชิกตัวปัจจุบันไปยังสมาชิกตัวหน้าสุดเพื่อหาชื่อเซต
วิธีที่จะทำให้การดำเนินการค้นหาไม่ต้องเสียเวลาไล่ในรายการโยงถึง Ω(n) ก็คือสำหรับทุก ๆ สมาชิกในรายการโยง ให้มีตัวชี้โยงมายังสมาชิกตัวแรกสุดของรายการโยง ซึ่งจะทำให้การดำเนินการค้นหา ใช้เวลาเพียงแค่ O(1) เท่านั้น แต่ข้อเสียของวิธีนี้ก็คือในการยูเนียน จะต้องมาไล่ปรับปรุงตัวชี้ของสมาชิกทั้งหลายใหม่ให้ถูกต้องด้วย ทำให้การยูเนียน เสียเวลา Ω(n) แทน
สำหรับวิธีที่ใช้ตัวชี้มาช่วยนั้น หากมีการเก็บความยาวของรายการโยงไว้ในทุกขณะด้วย จะสามารถเพิ่มความเร็วในการดำเนินการได้โดยใช้ฮิวริสติก weighted-union heuristic ซึ่งมีหลักการว่าแทนที่การยูเนียนจะนำรายการโยงทั้ง 2 มาต่อกันตรง ๆ ให้ตรวจสอบก่อนว่ารายการโยงใดสั้นกว่า แล้วจึงนำรายการโยงที่สั้นไปต่อหลังจากรายการโยงที่ยาว ซึ่งหากทำตามขั้นตอนดังกล่าวจะทำให้การดำเนินการสร้างเซต ค้นหา และยูเนียน รวม m ครั้ง บนโครงสร้างข้อมูลเซตไม่มีส่วนร่วมที่มีสมาชิกทั้งหมด n ตัว ใช้เวลา O(m + n log n)[1] ทั้งนี้หากไม่มีโครงสร้างข้อมูลที่ดีกว่ารายการโยงก็จะไม่สามารถทำให้เวลาในการดำเนินการเร็วกว่านี้ได้
สาเหตุที่การใช้ weighted-union heuristic ทำให้เวลาการดำเนินการทั้งหลายใช้เวลา O(m + n log n) มาจากเหตุผลที่ว่าการรวมรายการโยงขนาดสั้น ๆ เข้ากับรายการโยงขนาดยาว ๆ จะเสียเวลาเปลี่ยนตัวชี้ของรายการโยงขนาดสั้นเท่านั้น ดังนั้นกรณีเลวร้ายที่สุดก็จะเกิดจากการที่นำรายการโยงขนาดพอ ๆ กันมาต่อกันเสมอ ซึ่งจะทำให้การต่อแต่ละครั้งเสียเวลา O(n) แต่การที่นำมาต่อกันเช่นนี้ก็ทำให้เซตถูกยูเนียนเข้าด้วยกันอย่างรวดเร็ว ซึ่งโครงสร้างเซตไม่มีส่วนร่วมขนาด n จะมีการ ยูเนียน อย่างเลวร้ายได้มากสุดเพียง log n ครั้งเท่านั้น จึงทำให้เฉพาะการยูเนียนในกรณีเลวร้ายที่สุดเสียเวลา O(n log n)
ในการดำเนินการค้นหา ก็สามารถใช้ตัวชี้เพื่อไปยังสมาชิกตัวด้านหน้าสุดของรายการโยงได้ภายในเวลา O(1) ตามที่กล่าวมาแล้ว
แนวคิดในการนำเซตที่มีขนาดเล็กกว่าไปต่อเซตที่มีขนาดใหญ่กว่ายังปรากฏให้เห็นในโครงสร้างข้อมูลอื่น ๆ เช่นฮีปทวิภาค หรือฮีปฟีโบนัชชีอีกด้วย
เมนูนำทาง
โครงสร้างข้อมูลเซตไม่มีส่วนร่วม รายการโยงเซตไม่มีส่วนร่วมใกล้เคียง
โครงสร้างพื้นฐาน โครงสร้างของโลก โครงสร้างเปลือกหอย โครงสร้างผลึก โครงสร้างข้อมูลเซตไม่มีส่วนร่วม โครงสร้างกั้นระหว่างเลือดกับอัณฑะ โครงสร้างนิยม โครงสร้างทรงโค้ง โครงสร้างโมเลกุลของกรดนิวคลีอิก: โครงสร้างสำหรับกรดดีออกซีไรโบสนิวคลีอิก โครงสร้างข้อมูลแหล่งที่มา
WikiPedia: โครงสร้างข้อมูลเซตไม่มีส่วนร่วม http://code.activestate.com/recipes/215912-union-f... http://citeseer.ist.psu.edu/anderson94waitfree.htm... http://www.cs.unm.edu/~rlpm/499/uf.html http://www.lix.polytechnique.fr/~nielsen/Srmjava.j... http://portal.acm.org/citation.cfm?doid=364099.364... http://www.boost.org/libs/disjoint_sets/disjoint_s...