선택 트리
선택 트리의 개념
여러 개의 정렬된 리스트를 효율적으로 병합하기 위해 사용하는 특수한 트리 자료구조.
주로 합병 정렬 과정에서 비교 횟수를 최소화하여 성능을 향상시키는 데 활용된다.
합병 정렬
여러 개의 정렬된 리스트를, 완전한 순서를 유지하는 하나의 정렬된 리스트로 병합하는 것을 의미한다. 이 때 선택드리를 사용하면 비교 횟수를 줄여서 효율적인 병합이 가능하다. 예를 들어, k개의 정렬된 리스트를 병합할 때, 일반적으로 k-1번의 비교가 핋요하지만, 선택 트리를 이용하면 이러한 비교 횟수를 줄일 수 있다.
선택 트리의 종류
| 종류 | 영문명칭 | 설명 |
|---|---|---|
| 승자 트리 | Winner Tree | 각 내부 노드가 두 자식 노드 중 더 작은 값을 가진 노드를 승자로 선택해 저장하는 완전 이진 트리 즉, 각 노드의 값이 자신의 두 자식 노드의 작은 값과 같은 완전 이진 트리 최종적으로 루트 노드에는 가장 작은 값이 위치하게 됨 이러한 구조를 통해 다음으로 작은 값을 빠르게 찾을 수 있음 |
| 패자 트리 | Looser Tree | 각 내부 노드에 승자가 아닌 패자의 값을 저장하며 승자는 부모 노드로 올라가는 방식의 트리 루트 노드 위에 최상위 0번 노드를 두어 최종 승자를 저장한다. 이러한 구ㅗ조를 통해 다음으로 작은 값을 효율적으로 찾을 수 있다. |
승자 트리
패자 트리
계산 횟수 비교
| 구분 | 계산 횟수 |
|---|---|
| 일반 합병 정렬 | O(n log n) |
| 승자 트리 | O(n log k) |
| 패자 트리 | O(n log k) |
n : 전체 원소의 개수
k : 전체 리스트의 개수
따라서 여러 개의 정렬된 리스트를 병합할 때는 선택 트리를 활용하는 게 시간 복잡도 측면에서 더 효율적일 수 있다.