선택트리
합병 정렬
- 차례로 정렬된 k개의 데이터 목록을 순서를 유지하는 하나의 데이터 리스트로 만드는 과정
- 일반적으로 데이터 목록에서 가장 작은 값이나 가장 큰 값을 결정할 수 있음
- 선택 트리를 이용하여 비교 횟수를 줄일 수 있음
승자트리
- 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진 트리
- 작은 값이 스자가 되어 올라가는 토너먼트 경기와 유사
- 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
- 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨
- 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교단계 부터는 비교 횟수가 감소됨
- 재구성 과정에서 빈 리스트가 생기면 큰 값(무한)을 넣어 줌
패자트리
- 각 노드가 두 자식 노드 중에서 더 작은 값을 갖는 완전 이진 트리라는 점은 승자트리와 같지만 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐
- 최상위 0번 노드에는 최종 승자를 저장함
- 잎 노드들이 각 리스트의 head를 가리킴
- 트리의 각 내부 노드에는 승자가 아닌 패자를 저장함 (즉, 패자를 부모 노드에 저장하고 승자 부모의 부모 노드로 올라가서 다시 경쟁)
- 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장
- 0번 노드에 최소값이 있으므로 이 값을 제거하여 전체 리스트에 저장함
- 제거된 값을 가지고 있던 4번의 리스트의 헤드에 위치한 값 24를 패자트리에 올려 보내고 경쟁을 시킴
- 패자 트리를 재구성 함
숲
숲의 정의
- 분리된 트리 모임
- 0개 이상의 분리된 트리 집합
- 숲 : n(n>=0)개 이상의 분리된 트리의 집합
- 트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음
- 반대로 숲을 연결하면 트리를 만들 수도 있음
숲의 이진트리 변환
- 먼저 각 트리(Ti)를 이진 트리 (Ti^BT^)로 바꿈
- 이때 Ti^BT^의 루트는 왼쪽 서브트리만 가짐
- 다음은 Ti^BT^의 루트를 최상위 루트로 하고, 왼쪽 자식은 그 왼쪽 서브트리, 오른쪽 자식은 나머지들의 이진트리(BT2-n)가 되도록 함
