선택트리
합병 정렬에 사용하는 특수한 자료구조
승자 트리
- 부모 노드가 두 자식 노드보다 작은 값을 가지는 완전 이진트리
- 작은 값이 승자가 되어 올라가는 토너먼트 형식
- 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 한다.
- 루트노드의 값이 트리의 최솟값이 된다.
시간복잡도
O(nlogn)
구성 단계
- 정렬된 리스트들 중에 가장 최소/최대 값을 토너먼트 형식으로 리프노드에 위치시킨다.
- 리프노드에서 자식노드끼리 비교해서 최소/최대 값을 부모노드로 이동
- 최솟값/최댓값이 루트노드에 위치
재구성
- 루트 노드에 위치하게 된 최소/최대값을 포함한 노드의 값을 비우고 해당 값을 가지고 있던 리스트에서도 삭제한다.
- 데이터 하나가 없어진 리스트의 맨 위 값을 다시 리프노드에 올리고 토너먼트 진행
- 위 과정을 반복한다. 재구성 단계에서 빈 리스트가 생기면 큰 값을 넣어준다.
패자 트리
- 승자트리와 같이 각 노드가 두 자식 노드보다 더 작은 값을 가지는 완전이진트리로 루트 노드 위에 최상위 0번 노드를 가진다는 점이 다르다.
- 최상위 0번 노드에 최종 승자를 저장한다.
- 패자는 부모노드에 저장하고, 승자는 부모 노드로 올라가서 다시 비교한다.
- 패자를 노드에 올리고, 비교할 땐 승자끼리 비교한다.
재구성
- 리스트에서 0번 노드의 데이터를 삭제하고 새로 리프노드에 데이터를 올린 후 부모 노드와 비교한다.
- 부모노드와 자신이 가리키고 있는 승자값을 비교하여 패자를 부모노드 값에 넣고, 승자는 부모 노드의 승자값으로 변경한다.
