이 글에서는 데이터 구조의 중요한 개념인 토너먼트 트리(Tournament Tree)와 그 두 가지 변형인 승자 트리(Winner Tree), 패자 트리(Loser Tree)에 대해 자세히 알아봅니다.
토너먼트 트리는 n개의 외부 노드(단말 노드)와 n−1개의 내부 노드를 가진 완전 이진 트리(complete binary tree)입니다. 외부 노드는 경기에 참가하는 선수(키 값)를 나타내고, 내부 노드는 두 선수 간의 경기에서 승리한 사람을 나타냅니다. 이러한 구조적 특성 때문에 토너먼트 트리는 선택 트리(Selection Tree)라고도 불립니다.
토너먼트 트리의 주요 특징
루트가 있는 트리(Rooted Tree): 부모에서 자식으로 향하는 방향성 있는 경로가 존재하며, 부모가 없는 유일한 원소(루트)가 하나 있습니다.
부모-자식 값의 일관성: 일반적으로 부모의 값은 자식의 값보다 작거나 같습니다. 비교 연산자는 어떤 것을 사용해도 무방하지만, 부모와 자식 간의 상대적 대소 관계가 트리 전체에서 일관되게 유지되어야 합니다.
구멍(Hole)의 존재: 노드 수가 2의 거듭제곱이 아니면 트리에 빈 자리(구멍)가 생길 수 있으며, 이 구멍은 트리의 어느 위치에든 존재할 수 있습니다.
이진 힙의 일반화: 토너먼트 트리는 이진 힙(binary heap)을 적절히 일반화한 구조입니다.
전체 우승자: 루트 노드는 전체 토너먼트의 최종 우승자, 즉 최솟값 또는 최댓값을 나타냅니다.
토너먼트 트리는 크게 두 가지 유형으로 나눌 수 있습니다.
승자 트리(Winner Tree)
패자 트리(Loser Tree)
승자 트리(Winner Tree)
승자 트리는 각 내부 노드가 자신의 두 자식 노드 중 더 작은 값(최소 트리의 경우) 또는 더 큰 값(최대 트리의 경우)을 나타내는 완전 이진 트리입니다. 따라서 루트에는 항상 트리 전체에서 가장 작은 값 또는 가장 큰 값, 즉 토너먼트의 최종 우승자가 저장됩니다.
예시 − 키 값 3, 5, 6, 7, 20, 8, 2, 9로 최소 승자 트리를 구성하면, 루트에는 전체 최솟값인 2가 위치하게 됩니다.
승자 트리를 처음 구축하는 데는 O(n)의 시간이 걸리며, 우승자(최솟값 또는 최댓값)를 출력한 뒤 트리를 재구성하는 데는 O(log n)의 시간이 소요됩니다. 이러한 특성 덕분에 승자 트리는 외부 정렬(external sorting)이나 k-way 병합처럼 여러 시퀀스에서 반복적으로 최솟값·최댓값을 선택해야 하는 상황에서 매우 유용하게 활용됩니다.
패자 트리(Loser Tree)
패자 트리 역시 n명의 선수에 대해 n개의 외부 노드와 n−1개의 내부 노드를 가지는 완전 이진 트리입니다. 이름 그대로 내부 노드에는 각 경기의 패자가 저장된다는 점이 승자 트리와 가장 큰 차이입니다. 대신 전체 토너먼트의 최종 우승자는 별도의 위치인 tree[0]에 저장됩니다.
패자 트리의 가장 큰 장점은 트리 재구성의 효율성입니다. 우승자를 출력한 후 트리를 다시 구성할 때, 패자 트리에서는 잎(외부 노드)에서 루트까지의 경로에 있는 노드만 살펴보면 충분합니다. 반면 승자 트리에서는 해당 경로상 노드들의 형제(sibling) 노드까지 함께 확인해야 하므로, 패자 트리가 더 적은 비교 연산으로 재구성을 완료할 수 있다는 점에서 대안적인 표현 방식으로 널리 사용됩니다.
패자 트리 생성 과정
패자 트리를 만들려면 먼저 승자 트리를 생성해야 합니다.
예시 − 키 값 10, 2, 7, 6, 5, 9, 12, 1이 주어졌다고 가정해 보겠습니다. 먼저 이 값들로 최소 승자 트리(minimum winner tree)를 만듭니다.
그다음, 각 내부 노드에 해당 경기의 패자 값을 저장하면 패자 트리가 완성됩니다.
