선택 트리 합병 정렬 차례로 정렬된 k개의 데이터 목록을 순서를 유지하는 하나의 데이터 리스트로 만드는 과정 일반적으로 데이터 목록이 k개인 경우, k-1번 비교를 통해 데이터 목록에서 가장 작은 값이나 가장 큰 값을 결정할 수 있음 선택 트리를 이용하여 비교 횟수를 줄일 수 있음 승자 트리 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진 트리 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교단계부터는 비교 횟수가 감소됨 재구성 과정에서 빈 리스트가 생기면 큰 값(∞)을 넣어줌 패자 트리 각 노드가 두 자식 노드 중에서 ..