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

선택트리

합병 정렬 : 정렬된 k개의 데이터 리스트를 완전한 순서를 유지하는 하나의 데이터 리스트로 만드는 과정

선택 트리를 이용하여 비교 횟수를 줄일 수 있음

 

승자 트리 부모 노드가 자식 노드보다 작은 값을 갖는 완전 이진트리	패자 트리 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 트리
작은값이 승자가 되어 올라가는 토너먼트 경기와 유사 트리의 각 노드는 두 자식 노드값의 승자를 자신의 값으로 루트는 트리에서 가장 작은 값	루트 노드 위에 최상위 0번 노드를 가짐 트리의 각 내부노드에는 승자가 아닌 패자를 저장

 

숲

분리된 트리 모임

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

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

트리에서 루트를 제거하면 숲을 쉽게 얻을 수 있음

반대로 숲을 연결하면 트리를 만들 수도 있음

이진트리로 변경 후 숲으로 변경

 

이진 트리 개수

어떤 이진 트리에 대한 전위 순회 방문 순서와 중위 순회 방문 순서가 정해지면 트리 구조가 하나뿐임

 

---

정답 3