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

선택 트리가 왜 필요할까??

 

위 그림과 같이 정렬된 데이터 리스트 k개가 있다고 가정해 보자.

이 8개의 리스트를 전부다 합칠것인데 오름차순으로 정렬을 하여 합친다면 시간 복잡도는

k * k-1가 되는데 너무 많은 연산을 해야한다. 이러한 문제를 해결하기 위해 합병 정렬에 사용하는 특수한 트리가 있는데

그것을 선택트리 라고 한다.

 

선택 트리의 종류 2가지

 

1. 승자 트리

 

-승자 트리:== 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리

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

-트리의 각 노드는 두 자식 노드 값이 승자를 자신의 값으로 함

-결과적으로 루트의 값이 트리에서 가장 작은값

 

2.패자 트리

 

-패자 트리:== 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같지만, 패자트리는 루트 노드 위에 최상위 0번 노드를 가짐

- 최상위 0번 노드에는 최종 승자를 저장한다

-트리의 각 내부노드에는 승자가 아닌 패자를 저장

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

 

숲

빈 숲 - 홀로 숲 - 홀로 숲 - 숲

숲이란?

 

-분리된 트리 모임

-트리의 모임

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

 

숲을 이진 트리로 변환하는 원리

 

각 트리를 이진 트리로 바꾼 후 하나의 이진 트리로 구성한다.

 

이진 트리 개수

 

이진 트리 개수 공식

카탈랑이라는 수학자가 노드 n개인 서로 다른 이진 트리의 개수가 다음과 같음을 증명했었다.