Xem Tournament tree, Winner tree, Loser tree. Tournament tree là cây nhị phân hoàn chỉnh với n nút lá (người chơi) và n-1 nút nội (người thắng trận đấu giữa hai người). Còn gọi là Selection tree.
Đặc điểm:
- Cây có gốc, đường đi từ cha đến con, gốc duy nhất không có cha.
- Giá trị cha ≤ giá trị con (hoặc bất kỳ toán tử so sánh nào miễn là bất biến).
- Cây số nút không phải lũy thừa 2 có "holes" (lỗ trống) ở vị trí bất kỳ.
- Là tổng quát hóa của binary heap.
- Gốc đại diện người thắng chung cuộc.
Hai loại Tournament Tree:
- Winner Tree
- Loser Tree
Winner Tree
Winner tree là cây nhị phân hoàn chỉnh, mỗi nút đại diện cho nhỏ hơn (hoặc lớn hơn) hai con. Gốc giữ khóa nhỏ nhất/lớn nhất. Người thắng là khóa nhỏ nhất/lớn nhất trong tất cả dãy. Tạo winner tree trong O(log n).
Ví dụ – Khóa: 3, 5, 6, 7, 20, 8, 2, 9
Loser Tree
Loser tree: cây nhị phân hoàn chỉnh n người chơi, n nút lá, n-1 nút nội. Người thua được lưu ở nút nội. Nhưng người thắng chung lưu tại tree[0]. Ưu điểm: tái cấu trúc sau khi xuất winner chỉ cần kiểm tra nút trên đường từ lá đến gốc thay vì anh chị em.
Ví dụ – Tạo winner tree trước. Khóa: 10, 2, 7, 6, 5, 9, 12, 1.
Lưu người thua tại mỗi nút nội:
