[자료구조] 선택트리 , 숲 , 이진트리 개수

선택트리

합병 정렬

• 차례로 정렬된 k개의 데이터 목록을 순서를 유지하는 하나의 데이터 리스트로 만드는 과정
• 일반적으로 데이터 목록이 k개인 경우, k-1 번 비교를 통해 데이터 목록에서 가장 작은 값이나 가장 큰 값을 결정 할 수 있음
• 선택 트리를 이용해서 비교 횟수를 줄일 수 있음

승자트리

• 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진트리
• 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
• 결과적으로 루트의 값이 트리에서 가장 작은 값

→ 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교부터는 횟수가 감소 됨

→ 재구성 과정에서 빈 리스트가 생기면 큰 값을 넣어줌

패자트리

• 각 노드가 두 자식 노드 중에서 더 작은 값을 갖는 완전 이진트리 라는 점은 승자 트리와 같지만 패자트리는 루트 노드 위에 최상위 0번 노드를 가짐
• 최상위 0번 노드에는 최종 승자를 저장함
• 입 노드들이 각 리스트의 head를 가리킴
• 트리의 각 내부 노드에는 승자가 아닌 패자를 저장함

(즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)

• 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장

숲

숲의 정의

• 분리된 트리 모임
• 0개 이상의 분리된 트리 집합
• 트리에서 루트 ( 혹은 다른 노드) 를 제거 하면 숲을 쉽게 얻을 수 있음
• 반대로 숲을 연결하면 트리를 만들 수도 있음

이진 트리 개수

노드개수가 3개인 이진트리의 개수

• 전위 순회로 첫 번쨰 방문한 노드가 1이라면, 1은 루트
• 중위 순회 방문 순서는 1이 가장 먼저 나오므로 3,2 는 노드 1의 오른쪽 서브트리
• 전위 순회 두 번째 방문 노드가 2이고 중위 순회의 경우 3번 노드가 먼저 방문되므로 → 노드 3이 노드 2의 왼쪽 서브트리임