Winner Tree

1. Winner Tree란?

Winner Tree(승자 트리)는 n개의 external node와 n-1개의 internal node로 이루어진 complete binary tree이다.
Winner tree는 토너먼트의 대진표라고 생각하면 되는데, external node는 토너먼트의 모든 참가자, internal node는 경기 후 다음 라운드에 진출한 참가자를 의미한다.

2. 예시

위 그림과 같은 승자 트리가 있다고 하자. 이 트리에서 맨 아래에 있는 리프 노드들이 external node, 나머지 노드들이 internal node가 된다. 이 승자 트리는 값이 더 작은 값이 승자가 되어 위로 올라간다. 이렇게 하면 최종 승자가 이 트리의 최솟값이 되는데, 이러한 승자 트리를 Min Winner Tree라고 한다. 반대로 더 큰 값이 승자가 되어 최댓값이 최종 승자가 되는 승자 트리는 Max Winner Tree라고 한다.
트리의 높이(깊이)는 external node를 제외하면 $\log_2 n$가 된다.

3. 활용

승자 트리는 최댓값 혹은 최솟값을 구할 수 있다는 특징 덕분에 어떠한 배열을 정렬하는데에 사용할 수 있다. 다음은 min winner tree를 이용하여 오름차순으로 정렬하는 예시이다.

먼저, 모든 external node의 최솟값인 1을 배열에 넣는다. 그리고 가장 아래의 internal node에서 1 대신 8을 승자로 올린 후 승자를 다시 계산한다. 이렇게 하면 오른쪽 external node에 있던 1이 최종 승자가 된다.

최종 승자가 된 1을 배열에 넣고, 1 대신 4를 승자로 올리고 승자를 다시 계산한다. 이 경우 2가 최종 승자가 된다.

최종 승자가 된 2를 배열에 넣고, 2 대신 5를 승자로 올리고 승자를 다시 계산한다. 이 경우 3이 최종 승자가 된다.

최종 승자가 된 3을 배열에 넣고, 3 대신 6을 승자로 올리고 승자를 다시 계산한다. 이 경우 4가 최종 승자가 된다.

최종 승자가 된 4를 배열에 넣고, 4 대신 5를 승자로 올리고 승자를 다시 계산한다. 이 경우 5가 최종 승자가 된다.

최종 승자가 된 5를 배열에 넣고, 5 대신 6을 승자로 올리고 승자를 다시 계산한다. 이 경우 6이 최종 승자가 된다.

최종 승자가 된 6을 배열에 넣고, 6 대신 8을 승자로 올리고 승자를 다시 계산한다. 이 경우 8이 최종 승자가 된다. 마지막으로 8을 배열에 넣으면, external node들을 오름차순으로 정렬할 수 있다. 내림차순으로 정렬하고자 할 때에는 max winner tree를 사용하면 된다.

4. 시간 복잡도

• 각 노드의 값 비교: $O(1)$
• winner tree 초기화(최종 승자 결정): $O(n)$
• 승자를 삭제한 후 n번 반복(정렬): $O(n\log n)$

Loser Tree

1. Loser Tree란?

Loser Tree(패자 트리)는 winner tree와 같은 구조를 가지지만, 각 비교의 승자 대신 패자를 저장하는 트리이다.

2. 예시

위 그림과 같은 Min Loser Tree가 있다고 하자. 이 트리에서도 min winner tree와 똑같이 최솟값을 찾을 것이다. 따라서 두 리프 노드 중 더 작은 값을 승자로 올린다. 이때 첫 번째, 두 번째 internal node는 각각 3, 1이 되는데, 둘 중 더 작은 값인 1이 부모 노드로 올라가고, 원래 3, 1이 있던 자리는 각각의 패자인 6, 8이 저장된다.

오른쪽 서브 트리도 동일하게 진행된다. 세 번째, 네 번째 internal node는 각각 2, 1이 되고, 이 중 더 작은 값인 1이 부모 노드로 올라간다. 그리고 원래 2, 1이 있던 자리는 각각의 패자인 5, 4가 저장된다.

가장 위의 노드들 중 가장 작은 값은 1이므로, 왼쪽의 1이 승자로 올라가고, 기존에 1이 있던 자리는 패자였던 3이 저장된다.

패자 트리는 이렇게 승자를 정하고, 패자를 원래 자리에 저장한다.

3. 시간 복잡도

• loser tree 초기화(최종 승자 결정): $O(n)$
• 승자를 삭제한 후 n번 반복: $O(n\log n)$

다른 자료구조와의 비교

1. Winner Tree vs. Loser Tree

• Loser tree의 구현이 더 어렵다. Loser tree는 실시간 처리가 아닌 경우 잘 사용하지 않는다.
• Winner tree는 그에 반해 구현 과정에서 고려할 것이 더 적다.

2. Heap vs. Winner Tree

• Heap은 root 노드가 그 서브 트리의 최댓값, 최솟값인 것만 보장한다. 빠르고 효율적이고, 일반적으로 우선순위를 기준으로 정렬할 때 사용한다.
• Winner tree는 구성 과정이 조금 더 복잡하고 어렵지만, 다량의 데이터를 분산 처리할 때 효과적이다.

3. BST vs. Winner, Loser Tree

• BST는 중복 키값을 허용하지 않지만, Winner, Loser tree는 허용한다.
• 최댓값, 최솟값을 고를 때는 winner, loser tree가 더 좋다.
• 대량의 데이터를 처리하는 분산 환경에서는 loser tree가 더 효율적이다.
• 데이터가 지속적으로 수정되는 상황에서는 loser tree가 winner tree보다도 효율적이다.

4. 정리

Winner tree, loser tree는 주로 메모리 크기가 부족해서 이진 탐색이 불가능할 때, 즉 다량의 데이터를 처리할 때 사용된다. 그 중 데이터가 지속적으로 갱신되는 상황에서는 winner tree보다 loser tree가 더 효과적이다.