28. 승자트리와 패자트리

이진트리를 처음 접했을 때 가장 먼저 생각난 것은 토너먼트 대진표이다.

사람들의 생각이 비슷하다고 느낀 것은 이진트리를 활용한 토너먼트와 관련된 알고리즘과 자료구조가 존재한다.

 

토너먼트 알고리즘

토너먼트 알고리즘은 N개의 항목이 존재할 때, 이들을 두 개씩 짝지어 경기를 시키고, 이긴 항목을끼리 다시 경기를 시켜 이긴 항목을 또 다시 경기시키는 과정을 반복하여 마지막에 승자를 결정하는 알고리즘이다.

이 알고리즘에서 승자트리와 패지트리는 토너먼트 경기에서 승자와 패자를 효율적으로 추적하기 위해 사용되는 자료구조이다.

---

승자 트리

각 경기의 승자들을 이진 트리 형태로 구성하여 저장한다.

이진 트리의 각 노드는 해당 경기에서 승리한 항목을 나타내며, 상위 레벨의 노드에서는 하위 레벨에서의 승자들 중 가장 우수한 항목이 저장된다. 마지막으로 승자트리의 루트 노드에는 최종 승자가 저장된다.

---

패자 트리

승자 트리와는 반대로 각 경기에서 패배한 항목들을 저장한다.

패자 트리의 각 노드는 해당 경기에서 패배한 항목을 나타내며, 승자트리와 마찬자기로 최종적으로 패자트리의 루트 노드에는 최종 패자가 저장된다.

 

승자 트리와 패자 트리는 토너먼트 알고리즘에서 유용하게 사용되며, 대회, 경기 등에서 높은 성능을 요구하는 경우 많이 활용된다. 또한 승자트리와 패자트리는 다양한 탐색 알고리즘, 최적화 알고리즘 등에서도 사용된다.