ต้นไม้การแข่งขัน ต้นไม้ผู้ชนะ และต้นไม้ผู้แพ้ในโครงสร้างข้อมูล

ที่นี่เราจะเห็นต้นไม้การแข่งขัน ต้นไม้ Winner และ Looser ต้นไม้การแข่งขันเป็นต้นไม้ไบนารีที่สมบูรณ์ที่มี n โหนดภายนอกและ n – 1 โหนดภายใน โหนดภายนอกเป็นตัวแทนของผู้เล่น และโหนดภายในเป็นตัวแทนของผู้ชนะการแข่งขันระหว่างผู้เล่นสองคน ต้นไม้นี้เรียกอีกอย่างว่าต้นไม้การคัดเลือก

มีคุณสมบัติบางอย่างของต้นไม้การแข่งขัน เหล่านี้เป็นเหมือนด้านล่าง −

• ต้นไม้ต้นนี้หยั่งรากแล้ว ดังนั้นการโยงในแผนผังและเส้นทางจากพาเรนต์ถึงลูกและมีองค์ประกอบเฉพาะที่ไม่มีพาเรนต์

• ค่าพาเรนต์มีค่าน้อยกว่าหรือเท่ากับโหนดนั้นสำหรับตัวดำเนินการเปรียบเทียบทั่วไป สามารถใช้ได้ตราบใดที่ค่าสัมพัทธ์ของพาเรนต์และรายการย่อยไม่เปลี่ยนแปลงตลอดทั้งทรี

• ต้นไม้ที่มีจำนวนโหนดไม่ใช่ 2 มีรู หลุมสามารถปรากฏได้ทุกที่ในต้นไม้

• ต้นไม้นี้เป็นลักษณะทั่วไปที่เหมาะสมของไบนารีฮีป

• รากจะเป็นตัวแทนของผู้ชนะโดยรวมของการแข่งขัน

ต้นไม้การแข่งขันมีสองประเภท -

• ต้นไม้ผู้ชนะ

• ต้นไม้หลวม

แผนภูมิผู้ชนะ

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

ตัวอย่าง − สมมติว่ามีบางปุ่ม 3, 5, 6, 7, 20, 8, 2, 9

ต้นไม้หลวม

Looser Trees เป็นต้นไม้ไบนารีที่สมบูรณ์สำหรับผู้เล่น n คน โดยที่ n โหนดภายนอก และ n – 1 โหนดภายในที่มีอยู่ การจับคู่ที่หลวมจะถูกเก็บไว้ในโหนดภายใน แต่ในภาพรวมนี้ ผู้ชนะจะถูกเก็บไว้ที่ tree[0] ตัวคลายคือการแสดงทางเลือกที่เก็บการคลายการแข่งขันที่โหนดที่เกี่ยวข้อง ข้อดีของการคลายคือ การปรับโครงสร้างต้นไม้ใหม่หลังจากเอาท์พุตทรีผู้ชนะ การตรวจสอบโหนดบนเส้นทางจากลีฟหนึ่งไปอีกรูตนั้นเพียงพอแล้ว แทนที่จะตรวจสอบพี่น้องของโหนดบนเส้นทางนี้

ตัวอย่าง − ในการสร้างต้นไม้ที่หลวมกว่านี้ เราต้องสร้างต้นไม้ผู้ชนะก่อน

สมมติว่ามีบางคีย์ 10, 2, 7, 6, 5, 9, 12, 1 ดังนั้นเราจะสร้างแผนภูมิผู้ชนะขั้นต่ำในตอนแรก

ตอนนี้ เราจะเก็บค่าที่ตรงกันไว้ในแต่ละโหนดภายใน