[알고리즘] 최대 최소 찾기 (토너먼트 트리)

최대 최소 찾기

토너먼트 트리

선택트리(Selection tree) 라고도 하며, 이를 이용하면 여러개의 정렬된 묶음들(run) 중에서 가장 작은 값을 찾거나, 가장 큰 값을 찾을 때 이를 이용하면 비교횟수를 줄일 수 있다.

예를들어, 서울 경기 강원 충청 등등에서 각 지역마다 가장 키 큰 사람 100명씩을 뽑은 뒤에 

그 들 중에서 가장 키가 큰사람을 순서대로 뽑고 싶을 때 토너먼트 트리를 이용할 수 있다. 

 

토너먼트 트리에는 루트에 더 큰값을 올리느냐, 작은 값을 올리느냐에 따라 승자트리와 패자트리 두 종류가 있다.

승자 트리 (Winner Tree)

부모노드가 두 개의 자식노드보다 더 작은 값을 나타내는 완전 이진트리이다.

따라서 루트노드는 트리에서 가장 작은 원소이다.

오름차순으로 정리된 k개의 run에 대해 승자트리를 만드는 과정은 다음과 같다.

여러개의 run들 중에 가장 작은 값을 순차적으로 찾아나가는 트리이므로 각 run들은 오름차순(작은 값이 앞에 있도록)으로 정렬되어있어야 한다.

먼저, 아래와 같은 4개의 run들이 있다고 하자. 각 run들의 가장 첫번째 원소들을 대상으로 승자 트리를 만든다.

 

각 원소들을 비교해서 더 작은 원소를 위로 올리는 과정을 반복한다.

가장 작은 값이 루트노드에 올라온 것을 확인할 수 있다

 

이 상태에서 가장 작은 값(루트)을 삭제하게 되면, 해당 값이 들어있는 노드를 모두 삭제한다.

그 후에 값이 삭제된 run의 다음 원소를 비어있는 리프노드로 올린다

 

가장 아래에서부터 더 작은 원소를 위로 올리는 과정을 반복한다.

또다시 가장 작은 값이 루트노드에 올라온 것을 확인할 수 있다

이런 과정을 반복하면서 계속적으로 여러개의 run들 중에서 가장 작은 값들을 찾아낼 수 있다.

패자 트리 (Loser Tree)

승자트리와 개념이 같지만, 부모노드가 두 개의 자식노드보다 더 큰 값을 나타내는 완전 이진트리이다.

따라서 루트노드는 트리에서 가장 큰 원소이다.

내림차순으로 정리된 k개의 run에 대해 승자트리를 만드는 과정은 다음과 같다.

여러개의 run들 중에 가장 큰 값을 순차적으로 찾아나가는 트리이므로 각 run들은 내림차순(큰 값이 앞에 있도록)으로 정렬되어있어야 한다.

먼저, 아래와 같은 4개의 run들이 있다고 하자. 각 run들의 가장 첫번째 원소들을 대상으로 승자 트리를 만든다.

각 원소들을 비교해서 더 큰 원소를 위로 올리는 과정을 반복한다.

가장 큰 값이 루트노드에 올라온 것을 확인할 수 있다

이 상태에서 가장 큰 값(루트)을 삭제하게 되면, 해당 값이 들어있는 노드를 모두 삭제한다.

그 후에 값이 삭제된 run의 다음 원소를 비어있는 리프노드로 올린다

가장 아래에서부터 더 큰 원소를 위로 올리는 과정을 반복한다.

또다시 가장 큰 값이 루트노드에 올라온 것을 확인할 수 있다

이런 과정을 반복하면서 계속적으로 여러개의 run들 중에서 가장 큰 값들을 찾아낼 수 있다.

구현

토너먼트 트리의 경우 배열로 구현하는 것이 더 효율적이다

 

[구현 코드] -- 공부해서 추가할 것 

https://jaimemin.tistory.com/189

• https://bitbucket.org/vermapratyush/online-judges/src/2b22910da6fa3a07e820fb244c700b6e16c9e9f5/codes-sahni/completeWinnerTree.h?at=master&fileviewer=file-view-default

셀렉션 알고리즘

[추가할 것]

참고자료

https://codemcd.github.io/algorithm/Algorithm-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9/