선택트리,숲,이진트리 개수 ::= 자료구조

선택트리

합병정렬

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

합병정렬은 8개의 데이터목록에서 제일 상단 8개를 비교하여(7번비교하겠지) 제일 작은것은 뺄고 뺀 데이터목로 2번째숫자와 나머지 데이터목록 7개를 다시또 비교하여 제일작은것을 빼는것

 

이러한 합병정렬에서 선택트리는 가장 위에 있는 데이터를 자식노드에 놓고 작은 것을 찾아서 작은 것은 위로 부모로 올라가는 개념으로 생각하면 될 것 같다.

승자 트리라고 하며, 각노드가 두 자식노드의 작은 값을 갖는 완전전이진트리로 작은 값이 승자가 되어 올라가는 토너먼트 경기와 비슷하다. 트리의 각노드는 두 자식노드 값의 승자를 자신의 값으로 하고 결과적으로 루트의 값이 트리에서 가장 작은 값이 된다.  그러면 첫 번째 단계에서의 비교 횟수를 줄이지는 못하지만 두 번째부터는 데이터가 빠진 곳만 비교하면 되기 때문에 비교 횟수가 감소된다. 그리고 데이터목록이 모두 없어진 빈 리스트가 생기면 큰 값인 무한∞을 넣어준다.

 

패자트리는 처음에 데이터 목록을 잎노드에 놓는것은 동일하나 이후 올라간 데이터의 비교에서 패자를 부모노드로 올리고 승자를 부모의 부모노드로 올리는 것이다. 최종으로 가장 작은 수는 0번 노드, 2번째는 루트노드에 저장을 하게 된다.

따라서 0번 노드에 최소 값이 있으므로 이 값을 제거하여 전체 리스트에 저장한다. 제거된 값을 가지고 있던 리스트에서 가져와서 트리로 올려보네 경쟁을 다시 시킨다. 승자트리와 비교해서 승자트리는 새로운 값이 올라오면 올라온자리의 부모노드가 가리키는 반대편 자식노드의 값과 비교해야 돼서 복잡해지는데, 패자노드는 자신이 올라온자리의 부모노드와 비교한다는 장점이 있다.

 

숲

분리된 트리의 모임으로 0개 이상의 개별의 트리의 집합이다. 트리가 하나도 없다면 빈숲, 하나만 있다면 홀로 숲, 여러 개 트리가 있다면 숲이라고 한다. 쉽게 트리의 집합이 숲이다. 숲 : n(m >= 0)  개 이상의 분리된 트리의 집합. 트리에서 루트나 다른 노드를 제거하면 숲을 쉽게 얻을 수 있다. 반대로 숲을 연결하면 트리를 만들 수도 있다.

트리 T1, T2,..., Tn으로 구성된 숲에 대한 이진트리 BT_i~n은 다음과 같다고 할 수 있다.
n = 0 이면 BT₀는 빈이진트리
n = 1 이면 BT₁ = T₁^BT
n ≥ 2 이면

여기서 T₁^BT는 트리 T_i를(루트가 왼쪽 서브트만 갖도록 이진트리를 변환한 것을 말한다.

 

숲에서 이진트리의 변환은 먼저 각트리를 이진트리로 바꾼다. 이때에는 왼쪽 서브트리만을 갖게 된다. 이 때 이진트리의 호투를 최상위 루트로 하고 왼쪽 자신은 그 왼쪽 서브트리에 오른쪽 자식은 나머지들의 이진트리가 되도록 한다.

이진트리개수

노드와 이진트리의 관계

노드개수에 따라 가능한 이진트리 모양은 1개만 있을 때 2개만 있을 때 노드개수가 3개인 이진트리구조를 생각해 보자.

예를 들어 노드가 3개인 이진트리에서 전위 순회 방문 순서가 1,2,3, 인 이진트리는 다음과 같다.

 

예로 전위 순회로 방문한 첫 번째 노드가 1이라면 1은 루트가 된다. 중위 순회 방문순서에서 1이 먼저 나온다면 왼쪽 노드는 없다는 것을 알 수 있다. 전위순회의 두 번째 방문노드가 2이고 중위 순회에서 3이 두 번째로 나왔다는 것은 위 그림에서 두 번째에 해당하는 이진트리일 것이다. 이는 곧 어떤  이진트리에 대해서 전위순회와 중위 순회 방문 순서가 주어지면 트리의 구조를 유일한 한 개를 정의할 수 있다는 것이 된다.

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

1부터 n까지 수를 스택에 넣었다가 가능한 모든 방법으로 삭제하여 생성할 수 있는 경우의 수와 n개의 노드를 가진 상이한 이진트리의 수가 같다. 정위 순회 방문순서를 스택에 넣고 push / pop 연산을 이용한다면 중위 순회 방문 순서를 만들어 내면서 유일한 이진트리를 결정할 수 있게 된다.

스택을 이용해서 이진트리를 순회

push( )

트리생성과정으로 껍데기 노드와 왼쪽 서브트리를 나타낸다.
삽입될 노드보다 먼저 pop( )할 원소를 존재한다.
삽입될 노드의 왼쪽 서브트리가 될 노드가 존재한다.

pop( )

껍데기 노드에 값을 넣고 오른쪽 서브트리로 이동한다.
왼쪽 서브트리와 오른쪽 서브트리의 중간에 도달했다는 의미
중위순회에서 노드에 값을 넣은 후에 오른쪽 서브트리로 이동한다.

전위순회가 1,2,3이고 중위순회 방문순서가 1,3,2라면

연산	스택	출력
push( )	1
pop( )	-	1
push(2)	2	1
push(3)	2,3	1
pop( )	2	1,3
pop( )	-	1,3,2

push를 할 때는 빈껍데기가 생기고(트리의 노드값이 없는 상태) pop을 할 때는 다시 넣어준다.

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

(2n)! / n!(n+1)!