10-3. 이진트리 개수

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

 

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

- Push()는 트리 생성 과정으로 껍데기 노드와 왼쪽 서브트리를 나타냄

⇒ 삽입될 노드보다 먼저 pop() 할 원소가 존재함

⇒ 삽입될 노드의 왼쪽 서브트리가 될 노드가 존재함

 

- Pop()은 껍데기 노드에 값을 넣고 오른쪽 서브트리로 이동하는 것

⇒ 왼쪽 서브트리와 오른쪽 서브트리의 중간에 도달했다는 의미

⇒ 중위순회에서 노드에 값을 넣은 후에,오른쪽 서브트리로 이동함

 

10-1,2,3 정리하기

- 차례로 정렬된 데이터 리스트 k가 있다고 가정할 때 그것들을 완전한 순서를 유지하는 하나의 리스트로 만드는 과정을 합병 정렬이라고 합니다.

- 합병 정렬에 사용하는 특수한 트리가 선택트리입니다.

- 선택트리에는 승자트리와 패자트리 두 종류가 있습니다.

- 승자트리는 각 노드가 두 개의 자식노드 보다 더 작은 값을 갖는 완전 이진트리(실제로는 포화 이진트리)입니다.

- 승자트리 구축과정은 작은 값이 승자로 올라가는 토너먼트 경기와 유사합니다. 즉 트리의 각 내부 노드는 두 자식 노드 값의 승자를 자신의 값으로 합니다.

- 패자트리는 루트노드 위에 최상위 0번 노드를 갖습니다. 이 0번 노드에는 경쟁에서 이긴 최종 승자를 저장합니다.

- 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁합니다. 따라서 루트에는 마지막 토너먼트 패자를 저장하고 최종 승자는 0번 노드에 저장합니다.

- 분리된 트리 모임을 숲이라 부르며, 숲은 n(n≧0) 개 이상의 분리된 트리 집합입니다.

- 숲을 이진트리로 바꾸려면 먼저 각 트리(T_i)를 이진트리로 바꿉니다(T_i^BT). 이때 T_i^BT의 루트는 왼쪽 서브트리만을 같습니다.

- 다음은 T_i^BT의 루트를 최상위 루트로 하고 왼쪽 자식은 그 왼쪽 서브트리(오른쪽 서브트리는 없습니다) 오른쪽 자식은 나머지들의 이진트리(BT_2~n)가 되도록 합니다.

- 어떤 이진 트리에 대한 전위-중위 순회 방문 순서가 주어지면 트리 구조를 유일하게(한 개) 정할 수 있습니다.

- 1부터 n까지 수를 스택에 넣었다가 가능한 모든 방법으로 삭제하여 생성할 수 있는 경우의 수와 n개의 노드를 가진 상이한 이진트리의 수가 같습니다.

- 카탈란이라는 수학자가 노드 n개인 서로 다른 이진 트리의 개수가 (2n)!/n!(n+1)! 과 같음을 증명했습니다.