제 10장 선택 트리, 숲, 이진 트리 개수

1. 선택 트리
합병 정렬 - 차례로 정렬된 데이터 리스트 2개를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정.

선택 트리 - 합병 정렬에 사용하는 특수한 트리.

선택 트리 - 승자 트리와 패자 트리.
* 승자 트리 - 각 노드가 두 자식 노드의 작은 값인 완전 이진 트리.
* 승자 트리 구축 과정 - 작은 값이 승자로 올라가는 토너먼트 경기와 유사. 트리의 각 내부 노드는 두 자식 노드 값의 승자를 자신의 값으로 함. 결과로 루트 노드는 전체 토너먼트 승자, 트리에서 가장 작은 값을 갖는 노드가 됨. 루트가 결정되면 그 값을 전체 순서 리스트(k개 리스트를 합병한 리스트)에 출력하고 트리에서 삭제. 삭제한 데이터를 가지고 있던 리스트의 다음 데이터를 승자 트리로 올려 보내 승자 트 리를 재구성. 이 과정을 반복하여 k개의 리스트를 하나의 순서 리스트로 합병할 수 있음.

패자 트리 - 각 노드가 두 자식 노드 중 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같음. 잎 노드들이 각 리스트의 head가 가리키는 값(즉, 각 리스트의 가장 작은 값)을 갖는다는 점도 승자 트리와 같음.
****다른 점 - 패자 트리는 루트 노드 위에 최상위 0번 노드를 갖음. 이 0번 노드에는 경쟁에서 이긴 최종 승자를 저장.  내부 노드에는 (승자가 아니라) 토너먼트 패자를 저장. 즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁. 따라서 루트에는 마지막 토너먼트 (즉, 해당 라운드 결승전) 패자를 저장하고 최종 승자는 문제의 0번 노드에 저장.

2. 숲
* 숲 - 분리된 트리 모임.

- 하나의 트리로 구성된 숲.
- 노드가 한 개인 트리도 숲.
- 공집합도 트리로 인정.
숲 - n(>=0)개 이상의 분리된 트리 집합.
트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음. 숲을 연결하면 트리를 만들 수도 있음.

숲을 이진 트리로 변환하는 원리 - 먼저 각 트리를 이진 트리로 바꾼 후 하나의 이진 트리로 구성.
숲을 이진 트리로 바꾸려면 먼저 각 트리를 이진 트리로 바꾸는데 이때 T의 루트는 왼쪽 서브트리만 갖음. 다음은 T의 루트를 최상위 루트로 하고 왼쪽 자식은 그 왼쪽 서브트리, 오른쪽 자식은 나머지들의 이진 트리가 되게 함.