1. 개요
a. 런(run): 원소들이 정렬되어 있는 순서 순차(ordered sequence)
b. 합병 정렬: k개의 런(run)이 나뉘어진 n개이 언소들을 하나의 순서 순처로 합병하는 방식
-> 각 런은 key값에 따라 오름차순 정렬되어 있음
-> k개의 원소 중 가장 작은 키 값을 가진 원소를 선택: k-1번 비교
-> 선택트리 자료구조 이용 시 비교 회수 줄일 수 있음
2. 종류
a. 승리 트리(winner tree): 완전 이진트리
- 각 단말 노드는 런의 최소 키 값의 원소를 나타냄
- 내부 노드는 두 자식 중 가장 작은 키 값을 가진 원소로 나타남
- 구축과정: 가장 작은 키 값을 가진 원소가 승자, 트리에서 가장 작은 키 값을 가진 노드가 루트노드임으로 승자가됨
- 표현: 순차표현이 유리, 인덱스 i인 노드의 두 자식 인덱스는 2i와 2i+1에 위치
- 비교 횟수 = 승자 트리의 높이 = O(log n)
b. 패자 트리(loser tree): 루트 위 o번 노드가 추가된 완전 이진 트리
- 리프노드 = 각 런의 최소 키 값
- 내부 노드 = 패자 원소
- 루트(1번 노드)는 결승 토너의 패자를 나타내고, 전체 승자는 루트 위 별도로 위치한 o번 노드가 나타냄
- 구축과정: 단말 노드는 각 런의 최소 키 값을 갖는 노드
i) 내부 노드: 자식 노드들 토너먼트, 승자는 부모노드 위로 올라감
ii) 마지막 [1]번 루트 노드에서 경기: 승자는 전체 토너먼트 승자임으로 [0]번 노드에서 순차 출력
'알고리즘' 카테고리의 다른 글
| [Algorithm]그래프(Graph)의 정의 - 그래프의 표현 (2) | 2022.10.11 |
|---|---|
| [Algorithm]그래프(Graph)의 정의 - 그래프 추상 데이터 타입 (0) | 2022.10.11 |
| [Algorithm]힙(Heap)+ 우선순위Q (0) | 2022.10.11 |
| [Algorithm]이원 탐색 트리(Binary Search Tree) (0) | 2022.10.07 |
| [Algorithm]이진 트리 순회(Traversal) (0) | 2022.09.28 |