자료구조 28강 - 이진 트리

이진 트리(Binary Tree)

 

- 이진 트리의 정의

 

• Degree가 2인 트리
• 모든 노드는 최대 2개의 자식 노드를 가짐
• 모든 노드가 2개의 자식노드를 가짐(x)

 

- 이진 트리의 성질

 

1. i번째 레벨의 최대 노드의 수는 2^i-1개

(The maximum nodes in i-th level is 2^i-1)

 

• 수학적 귀납법을 통한 3단계 증명

i) induction basis ( n=1 일 때 성립함을 증명)

n=1 → root node의 레벨 → root node는 1=2^(1-1)=2^0

 

ii) induction hypothesis ( n=i 일 때 성립함을 가정)

n=i → i번재 레벨은 최대 2^(i-1)개의 노드를 가짐

 

iii) induction step ( n=i+1 일 때 성립함을 증명)

n=i+1 → (i+1)레벨이 최대 노드를 가지려면 i번째 레벨이 최대 노드를 갖고

그 노드들이 2개씩 child node를 가져야 함

 

따라서 (i+1)번째 레벨의 최대 노드의 수

→ 2^(i-1)개(i번째 레벨의 최대 노드 수) * 2(2개의 child)

=2^i=2^((i+1)-1)개의 노드를 가짐

 

 

2. Depth가 k인 이진 트리의 최대 노드는 2^k-1개

(The maximum nodes of a binary tree of depth k is 2^k-1)

 

• 수학적 귀납법을 통한 3단계 증명

i) induction basis ( n=1 일 때 성립함을 증명)

n=1 → depth=1인 트리 → root node만 있는 트리 → 1개=2^1-1

 

ii) induction hypothesis ( n=k 일 때 성립함을 가정)

n=k → depth=k인 이진 트리의 최대 노드 수 : 2^k-1개

 

iii) induction step ( n=k+1 일 때 성립함을 증명)

n=k+1 → (k+1)의 depth를 가진 이진 트리가 최대 노드를 가지려면

depth=k까지 최대 노드 + (k+1)레벨에서 최대 노드

→ 2^k-1+2^(k+1-1)개 → 2*2^k-1개 → 2^(k+1)-1개

 

 

3. 원소가 있는 이진 트리에 대해서 n[0]를 leaf node의 수,

n[2]를 degree가 2인 노드의 수라고 하면 n[0]=n[2]+1이 성립한다

 

• 직접 증명법을 통한 증명

i) 모든 노드의 수를 n개라고 하면 n=n[0]+n[1]+n[2]

ii) child node의 관점에서 보면 n=2n[2]+n[1]+1

iii) 따라서 n[0]+n[1]+n[2]=2n[2]+n[1]+1 → n[0]=n[2]+1

 

 

특별한 이진 트리

 

포화 이진 트리(Full binary tree)

 

• Depth가 k일 때 2^k-1개의 노드(최대 노드)를 갖는 이진 트리

 

완전 이진 트리(Complete binary tree)

 

• 같은 depth를 갖는 포화 이진 트리와 노드들 사이에 1:1 대응이 성립하는 이진 트리

 

 

트리 탐색(Tree Search)

 

- 탐색(Search or Traversal) : search(root node)

 

1. Root node로부터 시작해서 트리의 모든 노드를 방문하는 연산

2. 모든 트리에서 적용되는 일반적인 탐색

ⓞ 깊이 우선 탐색(Depth-first search, DFS)

ⓞ 넓이 우선 탐색(Breadth-first search, BFS)

3. 이진 트리에만 적용되는 특별한 탐색

 

cf. Search(A, x) : x ∈ A - return index / ~( x ∈ A ) - return null

 

- 이진 트리에서의 탐색

 

노드와 그 자식 노드를 방문하는 순서에 따라서 다음의 3가지 탐색이 가능하다

 

(1) 중위 우선 탐색(Inorder traversal) : 왼쪽 자식 노드  부모 노드 → 오른쪽 자식 노드 / BAC

void inorder(nptr bt){
	if(bt){
		inorder(bt->lchild);
		print(bt->data);
		inorder(bt->rchild);
	}
}

 

(2) 전위 우선 탐색(Preorder traversal) : 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 / ABC

void preorder(nptr bt){
	if(bt){
		print(bt->data);
		preorder(bt->lchild);
		preorder(bt->rchild);
	}
}

 

(3) 후위 우선 탐색(Postorder traversal) : 왼쪽 자식 노드 → 오른쪽 자식 노드  → 부모 노드 / BCA

void postorder(nptr bt){
	if(bt){
		postorder(bt->lchild);
		postorder(bt->rchild);
		print(bt->data);
	}
}

 

- 탐색 순서 예제 

 

 

• 중위 우선 탐색 : H D I B E A F C G
• 전위 우선 탐색 : A B D H I E C F G
• 후위 우선 탐색 : H I D E B F G C A