Tournament Tree
Complete Binary Tree มี External Nodes n ตัว และ Internal Nodes n-1 ตัว External Nodes = ผู้เล่น Internal Nodes = ผู้ชนะการแข่งขันระหว่าง 2 ผู้เล่น เรียกอีกอย่างว่า Selection Tree
คุณสมบัติ
- เป็น Rooted Tree มีทิศทาง Parent → Children มีรากเพียง 1 ตัว
- ค่า Parent ≤ (หรือ ≥) ค่า Children ใช้ Comparison Operator ใดๆ ได้
- ต้นไม้ที่จำนวนโหนดไม่ใช่กำลังของ 2 มี Holes (ช่องว่าง)
- เป็น Generalization ของ Binary Heaps
- Root = ผู้ชนะโดยรวมของ Tournament
2 ประเภท
- Winner Tree
- Loser Tree
Winner Tree
Complete Binary Tree แต่ละโหนดแทนค่าที่น้อยกว่า (หรือมากกว่า) ของลูก 2 ตัว Root เก็บค่าต่ำสุด (หรือสูงสุด) ทั้งต้นไม้ สร้างได้ใน O(log n)
ตัวอย่าง: Keys: 3, 5, 6, 7, 20, 8, 2, 9
Loser Tree
Complete Binary Tree n ผู้เล่น เก็บ Loser ของแต่ละคู่ใน Internal Nodes แต่ผู้ชนะโดยรวมเก็บที่ tree[0] ข้อดี: เมื่อ Restructure หลัง Winner Tree แสดงผล ต้องตรวจสอบโหนดบนเส้นทาง Leaf → Root เท่านั้น ไม่ต้องตรวจ Sibling
ตัวอย่าง: Keys: 10, 2, 7, 6, 5, 9, 12, 1 สร้าง Min Winner Tree ก่อน แล้วเก็บ Loser ใน Internal Nodes
