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

선택 트리

합병 정렬

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

승자 트리

• 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진 트리
• 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
• 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨
• 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교단계부터는 비교 횟수가 감소됨
• 재구성 과정에서 빈 리스트가 생기면 큰 값(∞)을 넣어줌

패자 트리

• 각 노드가 두 자식 노드 중에서 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같지만, 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐
• 최상위 0번 노드에는 최종 승자를 저장함
• 잎 노드들이 각 리스트의 head를 가리킴
• 트리의 각 내부 노드에는 승자가 아닌 패자를 저장함 (즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)
• 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장
• 패자 트리 재구성
  • 0번 노드에 최소값이 있으므로 이 값을 제거하여 전체 리스트에 저장함
  • 제거된 값을 가지고 있던 4번 리스트의 헤드에 위치한 값을 패자트리에 올려 보내고 경쟁을 시킴
  • 패자 트리를 재구성함

숲

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

숲의 이진트리 변환

트리 T_1, T_2, ..., T_n으로 구성된 숲에 대한 이진 트리 BT_i~n은 다음과 같다.
1. n=0이면 BT_0는 빈 이진 트리
2. n=1이면 BT_1=T_1^BT
3. n>=2이면       rootT_1^BT      
						    /          \\
		T_1^BT 왼쪽 서브 트리    BT_2~n
여기서 T_1^BT는 트리 T_i를 (루트가 왼쪽 서브 트리만 갖도록) 이진 트리로 변환한 것이다.

• 먼저 각 트리를 이진 트리로 바꿈
• 변환된 이진 트리의 루트를 최상위 루트로 하고, 왼쪽 자식은 그 왼쪽 서브트리, 오른쪽 자식은 나머지들의 이진 트리가 되도록 함

이진 트리 개수

노드 개수에 따른 가능한 이진 트리

노드 개수가 3인 이진 트리 구조

• 전위 순회 방문 순서가 1, 2, 3인 이진 트리

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

스택을 이용한 이진 트리의 순회

• push()
  • 트리의 생성 과정으로 껍데기 노드와 왼쪽 서브 트리를 나타냄
  • 삽입될 노드보다 먼저 pop()할 원소가 존재함
  • 삽입될 노드의 왼쪽 서브 트리가 될 노드가 존재함
• pop()
  • 껍데기 노드에 값을 넣고 오른쪽 서브 트리로 이동하는 것
  • 왼쪽 서브 트리와 오른쪽 서브 트리의 중간에 도달했다는 의미
  • 중위순회에서 노드에 값을 넣은 후에, 오른쪽 서브 트리로 이동함

선택 트리

합병 정렬

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

승자 트리

• 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진 트리
• 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
• 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨
• 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교단계부터는 비교 횟수가 감소됨
• 재구성 과정에서 빈 리스트가 생기면 큰 값(∞)을 넣어줌

패자 트리

• 각 노드가 두 자식 노드 중에서 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같지만, 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐
• 최상위 0번 노드에는 최종 승자를 저장함
• 잎 노드들이 각 리스트의 head를 가리킴
• 트리의 각 내부 노드에는 승자가 아닌 패자를 저장함 (즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)
• 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장
• 패자 트리 재구성
  • 0번 노드에 최소값이 있으므로 이 값을 제거하여 전체 리스트에 저장함
  • 제거된 값을 가지고 있던 4번 리스트의 헤드에 위치한 값을 패자트리에 올려 보내고 경쟁을 시킴
  • 패자 트리를 재구성함

숲

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

숲의 이진트리 변환

트리 T_1, T_2, ..., T_n으로 구성된 숲에 대한 이진 트리 BT_i~n은 다음과 같다.
1. n=0이면 BT_0는 빈 이진 트리
2. n=1이면 BT_1=T_1^BT
3. n>=2이면       rootT_1^BT      
						    /          \\
		T_1^BT 왼쪽 서브 트리    BT_2~n
여기서 T_1^BT는 트리 T_i를 (루트가 왼쪽 서브 트리만 갖도록) 이진 트리로 변환한 것이다.

• 먼저 각 트리를 이진 트리로 바꿈
• 변환된 이진 트리의 루트를 최상위 루트로 하고, 왼쪽 자식은 그 왼쪽 서브트리, 오른쪽 자식은 나머지들의 이진 트리가 되도록 함

이진 트리 개수

노드 개수에 따른 가능한 이진 트리

노드 개수가 3인 이진 트리 구조

• 전위 순회 방문 순서가 1, 2, 3인 이진 트리

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

스택을 이용한 이진 트리의 순회

• push()
  • 트리의 생성 과정으로 껍데기 노드와 왼쪽 서브 트리를 나타냄
  • 삽입될 노드보다 먼저 pop()할 원소가 존재함
  • 삽입될 노드의 왼쪽 서브 트리가 될 노드가 존재함
• pop()
  • 껍데기 노드에 값을 넣고 오른쪽 서브 트리로 이동하는 것
  • 왼쪽 서브 트리와 오른쪽 서브 트리의 중간에 도달했다는 의미
  • 중위순회에서 노드에 값을 넣은 후에, 오른쪽 서브 트리로 이동함