[자료 구조][알고리즘] 선택 트리(selection tree) - 승자 트리(winner tree),패자 트리(loser tree)
2018.12.11
선택 트리(selection tree) 하나의 순서 순차(ordered sequence)로 합병 될 런(run)이라 부르는 k개의 순서 순차가 있다고 가정하자. 각 런은 key라고 하는 지정된 필드에 따라 비감소 순서로 정렬된 약간의 레코드들로 구성된다. 선택 트리(selection tree) 자료 구조를 이용하면, 다음으로 가장 작은 레코드를 발겨하는데 필요한 비교 횟수를 줄일 수 있다. 선택 트리에는 승자 트리(winner tree)와 패자 트리(loser tree) 두 종류가 있다. 승자 트리(winner tree) 승자 트리는 각 노드가 2개의 자식 노드 중 더 작은 노드를 나타내는 완전 이진 트리이다. 그러므로 루트 노드는 트리에서 가장 작은 노드를 나타낸다. 각 리프들은 각 런에 첫번째 값이다..