자료구조 - 이진 트리 (Binary Tree)

1. 이진 트리란?

이진 트리(Binary Tree)란 트리의 분지 수(자식 노드의 개수)가 2 이하인 트리로 대부분의 트리 자료구조는 이진 트리 형태에서 나온다. 

 

2. 이진 트리의 종류

1) 정 이진 트리 (Full Binary Tree)

- 모든 노드의 차수가 0 또는 2인 이진 트리

 

2) 포화 이진 트리 (Perfect Binary Tree)

- 정 이진 트리에서 모든 단말 노드의 깊이가 같은 이진 트리

- 높이가 H인 포화 이진 트리의 노드 개수는 2^H-1개이다.

- 반대로 노드가 N개인 포화 이진 트리의 높이는 log(N+1)이다.

- 깊이가 D인 포화 이진 트리의 단말 노드 개수는 2^D개이다.

 

3) 완전 이진 트리 (Complete Binary Tree)

- 마지막 레벨은 노드가 왼쪽에 몰려있고 마지막 레벨을 제외하면 포화 이진 트리 구조를 띄고 있는 이진 트리

 

4) 사향 이진 트리 (Skewed Binary Tree)

- 연결리스트처럼 한 줄로 연결 되어 있는 형태의 이진 트리

 

3. 이진 트리의 표현

1) 연결 자료 구조

- 연결 리스트 형태의 자료구조

class Node
	Object data
    Node left_child, right_child

 

2) 연속 구조

- 일차원 배열을 이용한 구현

배열에 트리 노드를 레벨 순서대로 왼쪽에서 오른쪽으로 저장한다. 완전 이진 트리로 가정하고 배열의 1번 위치부터 저장을 시작한다고 가정했을 때 i번 노드의 부모, 왼쪽 자식, 오른쪽 자식을 구하는 방법은 다음과 같다.

function Parent(i)
	return i/2

function Left_child(i)
	return i*2

function Right_Child(i)
	return i*2+1

 

4. 이진 트리의 순회

트리는 비 선형 자료구조이기 때문에 모든 노드를 for문 한 번으로 방문이 불가능하다. 이런 트리 구조에서 모든 노드를 방문하기 위한 과정을 트리의 순회라고 한다. 특히 이진 트리의 순회는 왼쪽 자식 탐색, 오른쪽 자식 탐색, 현재 노드 방문의 세 가지 주요 과정을 통해 진행 되며, 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후외 순회로 나뉜다. 모든 순회는 루트노드에서 시작한다.

1) 전위 순회 (pre-order)

현재 노드 방문 - 왼쪽 자식 탐색 - 오른쪽 자식 탐색

A-B-G-H-D-C-E-F-I

 

2) 중위 순회 (in-order)

왼쪽 자식 탐색 - 현재 노드 방문 - 오른쪽 자식 탐색

G-B-H-D-A-C-F-E-I

 

3) 후위 순회 (post-order)

왼쪽 자식 탐색 - 오른쪽 자식 탐색 - 현재 노드 방문

G-D-H-B-F-I-E-C-A

 

5. 이진 트리의 응용

1) 힙

2) 인덱스 트리

3) 트라이