선택트리1 [개념] 선택트리 selection tree - 승자트리 winner tree, 패자트리 loser tree 선택트리에 대해 알아보겠습니다. ▣ 선택 트리 선택트리는 합병 정렬에 사용하는 특수한 구조를 가지는 트리 자료구조다. 그럼 합병정렬이란 어떤 알고리즘인가? ● 합병정렬 각각 차례로 정렬된 n개의 데이터 리스트들을 완전한 순서를 유지하는 하나의 리스트로 병합하는 과정이다. 각 리스트의 최솟값(최댓값)들을 비교해야 하기 때문에 한 번 합칠때마다 (n-1)번의 비교횟수가 필요하다. -> 낭비 그!래!서! 선택 트리를 이용하여 비교횟수를 줄인다. 누군가가 선택트리 중 하나인 승자트리라는 것을 고안해냈다. 선택트리에는 승자트리와 패자트리가 있다. 각각의 개념에 대해 알아보자. ● 승자 트리 winner tree (선택 트리 중 하나) 부모 노드가 두 자식 노드보다 작은 값을 가지는 완전이진트리다. 작은 값이 승자.. 2020. 9. 23. 이전 1 다음 반응형
