자료구조 강의 10화 :: 선택트리, 승자트리, 패자트리, 숲

자료구조 10화를 듣고 배운내용

 

 

KEYWORDS

• 합병 정렬(=병합 정렬 =Merge Sort): 정렬된 k개의 데이터 리스트를 하나의 리스트로 만드는 과정
  
  
• 선택 트리: 합병 정렬에 사용되는 특수한 트리
  
  
• 승자 트리: 자식노드보다 더 작은 값(승자)을 갖는 완전 이진트리
  
  
• 패자 트리: 자식노드보다 더 큰 값(패자)을 가지며, 최종 승자는 0번 노드에 저장
  
  
• 숲: 분리된 트리 모임, 0이상 n개 이상의 분리된 트리의 집합

 

 

선택 트리

일반적으로 k개일 때 k-1번 비교를 한다.

선택 트리를 이용해서 비교 횟수를 줄일 수 있다.

 

 

승자 트리

첫 번째 단계는 비교 횟수가 같지만,

두 번째 단계부터는 비교 횟수가 줄어든다.

작은 값이 승자가 되어 올라가는 토너먼트 경기

루트값이 트리에서 가장 작은 값이 된다.

 

 

패자 트리

두 노드를 비교해서 패자를 올리는 트리

 

 

숲(Forest)

분리된 트리의 모임

0개 이상의 분리된 트리 집합

루트를 자르면 트리가 여러 개 생기겠지 그게 숲이다.

 

숲을 이진트리로 만들어서 코드도 관리도 쉽게한다.

 

 

Tournament by Joshua Golde #unsplash