[개념] 선택트리 selection tree - 승자트리 winner tree, 패자트리 loser tree

선택트리에 대해 알아보겠습니다. 

▣ 선택 트리

선택트리는 합병 정렬에 사용하는 특수한 구조를 가지는 트리 자료구조다. 그럼 합병정렬이란 어떤 알고리즘인가?

 ●  합병정렬

합병정렬 ref. wikipedia

• 각각 차례로 정렬된 n개의 데이터 리스트들을 완전한 순서를 유지하는 하나의 리스트로 병합하는 과정이다.
• 각 리스트의 최솟값(최댓값)들을 비교해야 하기 때문에 한 번 합칠때마다 (n-1)번의 비교횟수가 필요하다. -> 낭비
• 그!래!서! 선택 트리를 이용하여 비교횟수를 줄인다.
• 누군가가 선택트리 중 하나인 승자트리라는 것을 고안해냈다.

 

 

선택트리에는 승자트리와 패자트리가 있다. 각각의 개념에 대해 알아보자.

 ● 승자 트리 winner tree (선택 트리 중 하나)

• 부모 노드가 두 자식 노드보다 작은 값을 가지는 완전이진트리다.
• 작은 값이 승자가 되어 올라가는 토너먼트 형식이다.
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 한다.
• 루트노드의 값이 트리의 최솟값이 된다.

 ● 승자 트리 구성 단계

   ① 최초 승자 트리 구성

1. 정렬된 리스트들 중에 가장 최소/최대 값을 토너먼트 형식으로 리프노드에 위치시킨다.
2. 리프노드에서 자식노드끼리 (둘 씩) 비교해서 최소/최대 값을 부모노드로 이동시킨다.
3. 최솟값/최댒값이 루트노드에 위치하게 된다.

 

  ② 승자 트리 재구성

1. 루트 노드에 위치하게 된 최소/최대 값을 포함한 노드의 값을 비우고 해당 값을 가지고 있던 리스트에서도 삭제한다.
2. 데이터 하나가 없어진 리스트의 맨 위 값(최소/최대)을 다시 리프노드에 올리고 토너먼트를 진행한다.
3. 위 과정을 반복한다. 재구성 단계에서 빈 리스트가 생기면 큰 값(inf)을 넣어준다.

 

 

☞ 승자 트리 첫 단계에서는 비교 횟수를 줄이지 못하지만, 승자 트리를 재구성할 때는 비교가 몇 번 발생하지 않는 것을 알 수 있다. 위 경우에서도 (22-24) / (14-22) / (14-12) 로 단 3번의 비교만에 최솟값을 가려냈다. (효율적!)

리스트가 비면서 리프 노드가 빈 노드가 되면 inf을 넣어줘서 비교연산이 계속 수행될 수 있게 한다. 위 사진에서는 굳이 쓰진 않았다. 

.

.

.

이런 식으로 하면 마지막 재구성 때는 아래와 같은 결과를 볼 수 있다. 빈 노드에는 inf 대신 적당히 큰 수인 999를 썼다.

 

 ● 패자트리 loser tree

• 승자트리와 같이 각 노드가 두 자식 노드보다 더 작은 값을 가지는 완전이진트리로, 루트 노드 위에 최상위 0번 노드를 가진다는 점이 다르다.
• 최상위 0번 노드에 최종 승자를 저장한다.
• 패자는 부모노드에 저장하고, 승자는 부모의 부모 노드로 올라가서 다시 비교한다.
• 루트노드에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장한다.

   ① 최초 패자 트리

• 패자를 노드에 올리고, 비교할 땐 승자끼리 비교한다.

 

  ② 승자 트리 재구성

• 리스트에서 0번 노드의 데이터를 삭제하고 새로 리프 노드에 데이터를 올린 후 부모노드와 비교한다.

 

• 부모노드와 자신이 가리키고 있는 승자값을 비교하여 패자를 부모노드 값에 넣고, 승자는 부모노드의 승자값으로 변경한다.

 

• 위 과정을 반복한다. 트리 재구성 할 때 비교횟수가 다른 자료구조에 비해 적어진다.