เมนูนำทาง
โครงสร้างข้อมูลเซตไม่มีส่วนร่วม ป่าไม้เซตไม่มีส่วนร่วมป่าไม้เซตไม่มีส่วนร่วมเป็นโครงสร้างข้อมูลซึ่งจะใช้โครงสร้างข้อมูลต้นไม้ในการแทนแต่ละเซต และโครงสร้างข้อมูลต้นไม้นี้ก็จะจัดเก็บโดยใช้รูปแบบ Spaghetti stack กล่าวคือแต่ละจุดยอดจะโยงไปยังพ่อของตัวมัน ป่าไม้เซตไม่มีส่วนร่วมได้มีการคิดค้นโดย Bernard A. Galler และ Michael J. Fischer ใน พ.ศ. 2507[2] โดยที่การวิเคราะห์ประสิทธิภาพของโครงสร้างข้อมูลนี้อย่างละเอียดตามมาหลังจากนั้นหลายปี
ในป่าไม้เซตไม่มีส่วนร่วมจะกำหนดให้ตัวแทนของแต่ละเซตคือจุดยอดที่เป็นรากของต้นไม้ ดังนั้นการดำเนินการค้นหา ก็คือการกระโดดสูงขึ้นไปเรื่อย ๆ จนกว่าจะเจอราก ส่วนการยูเนียนก็คือการดำเนินการค้นหากับต้นไม้ทั้งสองต้นเพื่อหารากของต้นไม้ทั้งสอง และนำรากของต้นไม้หนึ่งไปต่อกับรากของต้นไม้อีกต้น อาจเขียนเป็นรหัสเทียมออกมาได้ดังนี้
1 function MakeSet(x)2 x.parent := x
1 function Find(x)2 if x.parent == x3 return x4 else5 return Find(x.parent)
1 function Union(x, y)2 xRoot := Find(x)3 yRoot := Find(y)4 xRoot.parent := yRoot
อย่างไรก็ตาม ประสิทธิภาพของป่าไม้เซตไม่มีส่วนร่วมข้างต้นแย่กว่าการใช้รายการโยงเซตไม่มีส่วนร่วมแบบอย่างง่ายเสียอีก เพราะต้นไม้ที่เกิดขึ้นอาจจะไม่สมดุลเป็นอย่างมาก ในกรณีเลวร้ายมากที่สุดอาจถึงขั้นกลายเป็นเส้นตรงเลย ซึ่งจะทำให้การดำเนินการทั้งค้นหาและยูเนียน แต่ละครั้งใช้เวลา O(n) อย่างไรก็ตามขั้นตอนวิธีนี้สามารถเพิ่มประสิทธิภาพได้ 3 วิธี
วิธีแรก เรียกว่า union by height ใช้แนวคิดว่าให้นำต้นไม้ที่มีความสูงต่ำกว่าไปต่อต้นไม้ที่มีความสูงมากกว่าเสมอเหมือนแนวคิดของ weighted-union heuristic ด้วยวิธีนี้จะทำให้ต้นไม้มีความสูงเพิ่มขึ้นก็ต่อเมื่อนำต้นไม้ที่มีความสูงเท่ากันพอดีมายูเนียนกัน และความสูงจะเพิ่มเพียงแค่ 1 ด้วย ดังนั้นเนื่องจากสามารถมีการยูเนียนได้เพียง log n ครั้ง ความสูงของต้นไม้จึงเป็น log n ด้วย ส่งผลให้การดำเนินการทั้งค้นหา และยูเนียน ในแต่ละครั้งใช้เวลา O(log n) สามารถเขียนเป็นรหัสเทียมได้ดังนี้
1 function MakeSet(x)2 x.parent := x
1 function Find(x)2 if x.parent == x3 return x4 else5 return Find(x.parent)
1 function Union(x, y)2 xRoot := Find(x)3 yRoot := Find(y)4 xRoot.parent := yRoot
วิธีที่สองเรียกว่า การอัดวิถี โดยเป็นการที่พยายามทำให้โครงสร้างต้นไม้แบนราบเมื่อมีการดำเนินการค้นหา แนวคิดมาจากการที่การดำเนินการค้นหาแต่ละครั้งต้องวิ่งไล่ในวิถีผ่านจุดยอดต่าง ๆ จนถึงจุดยอดรากอยู่แล้ว ดังนั้นเมื่อทราบแล้วว่าจุดยอดรากคืออะไร ก็จะเปลี่ยนให้แต่ละจุดยอดบนวิถีดังกล่าวมีพ่อเป็นจุดยอดรากโดยตรงเลย ซึ่งเป็นการเพิ่มความเร็วในการดำเนินการค้นหาในครั้งถัด ๆ มา อย่างเห็นได้ชัด การเปลี่ยนความสัมพันธ์เช่นนี้ไม่ทำให้เกิดปัญหาใด ๆ ทั้งสิ้นเนื่องจากในการเปลี่ยนแปลงนี้ไม่ได้ทำให้จุดยอดรากเปลี่ยนไป ทำให้ตัวแทนเซตยังเหมือนเดิม และจุดยอดในต้นไม้ดังกล่าวก็ยังคงอยู่ในต้นไม้ต้นเดิมหลังเปลี่ยนแปลงโครงสร้างแล้ว ดังนั้นการเปลี่ยนแปลงโครงสร้างจึงทำให้เซตที่แทนออกมามีลักษณะเหมือนก่อนการเปลี่ยนแปลงทุกประการ ตัวอย่างรหัสเทียมของฟังก์ชัน find ที่ใช้ในการดำเนินการค้นหาคือ
1 function Find(x)2 if x.parent != x3 x.parent := Find(x.parent)4 return x.parent
เมนูนำทาง
โครงสร้างข้อมูลเซตไม่มีส่วนร่วม ป่าไม้เซตไม่มีส่วนร่วมใกล้เคียง
โครงสร้างพื้นฐาน โครงสร้างของโลก โครงสร้างเปลือกหอย โครงสร้างผลึก โครงสร้างข้อมูลเซตไม่มีส่วนร่วม โครงสร้างกั้นระหว่างเลือดกับอัณฑะ โครงสร้างนิยม โครงสร้างทรงโค้ง โครงสร้างโมเลกุลของกรดนิวคลีอิก: โครงสร้างสำหรับกรดดีออกซีไรโบสนิวคลีอิก โครงสร้างข้อมูลแหล่งที่มา
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...