การรวมตามอันดับและองค์ประกอบ

การ union แบบพื้นฐานเพียงแขวนรากหนึ่งไว้ใต้รากอีกต้น หากทำโดยไม่ระวัง อาจสร้างต้นไม้สูงที่ทำงานช้าได้ เราจึงต้องมีวิธีที่ฉลาดกว่าในการรวมราก

การ union ตามอันดับจะนำต้นไม้ที่เตี้ยกว่าไปไว้ใต้ต้นไม้ที่สูงกว่าเสมอ การรักษาให้ต้นไม้ตื้นทำให้การ find ในภายหลังรวดเร็วยิ่งขึ้น 📏

อันดับคือค่าประมาณความสูงของต้นไม้ องค์ประกอบแต่ละตัวเริ่มต้นด้วยอันดับ 0 เนื่องจากโหนดเดี่ยวไม่มีความลึกอยู่ด้านล่าง

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

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

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

เริ่มนับที่ n เนื่องจากองค์ประกอบทุกตัวเป็นกลุ่มของตัวเอง การ union ที่สำเร็จแต่ละครั้งจะรวมสองกลุ่มเป็นหนึ่งกลุ่ม ดังนั้นจึงลดค่าลงหนึ่ง

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

รวมการ union ตามอันดับเข้ากับการบีบอัดเส้นทาง แล้ว DSU จะทำงานในเวลาแบบอินเวอร์ส-แอกเคอร์มันน์ ซึ่งแทบจะเป็นค่าคงที่สำหรับข้อมูลนำเข้าจริงทุกชนิด ⚡

เมื่อใช้การ union ตามขนาด คุณสามารถตอบได้ทันทีว่ากลุ่มใดมีขนาดเท่าไร เพียงอ่านขนาดที่เก็บไว้ ณ รากขององค์ประกอบนั้น

การนับองค์ประกอบช่วยตอบคำถามคลาสสิก เช่น มีวงเพื่อนหรือบริเวณที่เชื่อมต่อกันกี่แห่ง หลังจากเรียกการรวมกลุ่มหลายครั้ง 🌐

ลองพิจารณาว่าตัวนับองค์ประกอบเปลี่ยนแปลงอย่างไร

คุณได้เรียนรู้การรวมกลุ่มตามอันดับเพื่อทำให้ต้นไม้แบนลง รวมถึงวิธีติดตามจำนวนองค์ประกอบและขนาดของกลุ่ม ตอนนี้ DSU ทำงานได้เร็วมากแล้ว! 🎉