학습개요
차례로 정렬된 데이터 리스트 k를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정을 합병 정렬 이라고 합니다. 이 합병 정렬에 사용하는 트리가 선택트리입니다. 선택트리를 구성하는 방법에는 승자트리와 패자트리가 있습니다.
승자트리는 각 노드가 두 개의 자식노드 보다 더 작은 값을 갖는 완전 이진트리입니다. 작은 값이 승자로 올라가는 토너먼트 경기와 유사하다고 할 수 있습니다. 패자트리는 루트노드 위에 최상위 0번 노드를 갖습니다. 이 0번 노드에는 경쟁에서 이긴 최종 승자를 저장합니다. 즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁합니다. 여기서는 승자트리와 패자트리를 구성하는 방법을 정확하게 알고 가시면 됩니다.
다음으로, 분리된 트리 모임을 숲이라 부릅니다. 트리에서 루트 또는 다른 노드를 제거하면 숲을 쉽게 얻을 수 있습니다. 반대로 숲을 연결하면 트리를 만들 수도 있습니다. 숲을 이진트리로 만들어보는 방법을 이해하면 됩니다. 그리고 노드가 n개일 때 서로 다른 이진트리의 개수를 알 수 있는 방법을 설명합니다. 순회방법을 이용하는 방법과 스택을 사용하는 방법을 설명하고 카탈란이라는 수학자가 정의한 공식에 대해서도 설명합니다.
학습목표
- 선택트리의 정의를 이해할 수 있다.
- 승자트리와 패자트리의 구성 단계를 이해할 수 있다.
- 숲의 개념과 숲을 이진트리로 변환하는 방법을 이해할 수 있다.
- 노드가 개인 서로 다른 이진트리의 개수를 알 수 있다.
연습문제
- 차례로 정렬된 데이터 리스트
k를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정을 무엇이나 하는가 ?
- 승자 트리
- 패자 트리
- 이진 선택 정렬
- 합병 정렬
–
- 각 노드가 두 개의 자식노드 보다 더 작은 값(승자)을 갖는 완전 이진트리는 무엇인가 ?
- 승자 트리
- 패자 트리
- 숲
- 이진 정렬
–
- 지문의 그림에서 마지막 패자는 무엇인가 ?
1. 14 2. 11 3. 12 4. 17
정리하기
