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

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

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

KEYWORDS

합병 정렬(=병합 정렬 =Merge Sort) : 정렬된 k개의 데이터 리스트를 하나의 리스트로 만드는 과정

: 정렬된 k개의 데이터 리스트를 하나의 리스트로 만드는 과정 선택 트리 : 합병 정렬에 사용되는 특수한 트리

: 합병 정렬에 사용되는 특수한 트리 승자 트리 : 자식노드보다 더 작은 값(승자)을 갖는 완전 이진트리

: 자식노드보다 더 작은 값(승자)을 갖는 완전 이진트리 패자 트리 : 자식노드보다 더 큰 값(패자)을 가지며, 최종 승자는 0번 노드에 저장

: 자식노드보다 더 큰 값(패자)을 가지며, 최종 승자는 0번 노드에 저장 숲: 분리된 트리 모임, 0이상 n개 이상의 분리된 트리의 집합

선택 트리

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

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

승자 트리

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

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

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

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

패자 트리

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

숲(Forest)

분리된 트리의 모임

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

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

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

Tournament by Joshua Golde #unsplash

from http://forgottenknowledge.tistory.com/148 by ccl(A) rewrite - 2021-10-11 14:00:35