자료구조 트리(Tree) 개요, 트리 탐색 방법

1. 개요

트리는 아래의 형태로 구현된다.

 

           A

       B        C

     D   E     F    G

      H       I  J     K

이런 트리가 있다고 쳤을 때, A는 Root(트리의 시작점)이다. 노드를 연결하는 노드 간선을 edge라고 한다.
A와 B, C를 연결하는 간선을 그리진 않았지만, edge로 이어졌다고 생각하면 된다.

 

노드간의 관계는

• 상위에 있는 노드는 parent
• parent 아래의 노드를 children
• 같은 parent를 가진 노드를 형제 노드
• 각 노드의 자식 수는 degree 라고 한다. (children 노드가 3개면 degree는 3이다.
• 자식이 없는 노드를 leaf 라 부르고, 터미널 노드라고도 부른다.
• 노드에서 다른 노드에 이르는 경로를 path라 부른다. path는 중복 경로를 포함하지 않는다.

노드의 구조는

• 노드의 깊이를 depth라 한다. Root를 기준으로, 자식이면 depth1, 자식의 자식이면 depth2다.
• 같은 depth를 가진 노드의 집단을 level로 부른다.
• 루트는 level-1, 루트의 자식들은 level-2, level-2의 자식들은 level-3, depth3 의 노드들은 level-3이다.

노드의 특징은

• 트리는 하위 노드가 Sub Tree를 구성할 수 있다는 재귀적인 특성을 가지고 있다. (Root의 자식을 기준으로 그 노드도 Root가 될 수 있다.)
• 노드는 왼쪽에서 오른쪽으로 채워짐
• 비선형적 자료구조
• 그래프의 한 종류

트리 중, 자식 노드가 최대 2개 (0~2)인 트리를 이진 트리라 한다.

이진 트리의 종류는

• 정 이진 트리 (Full Binary Tree, Stric Binary Tree) : 모든 노드가 2개의 자식을 가지거나, 자식이 없는 트리
• 포화 이진 트리 (Perfect Binary Tree) : 1. 모든 노드가 2개의 자식 노드를 가지고, leaf 노드가 같은 레벨일 때
• 2. 높이가 h인 포화 이진 트리에서 노드의 개수는 2^(h+1) - 1 이 된다. (Root만 있으면2^(0+1)-1 = 1, depth1 이면                2^(1+1)-1 = 3, depth2면 2^(2+1)-1 =7 개가 된다.)
• 3. leaf의 개수는 2^h
• 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외한 모든 노드가 채워져야 하는 트리 (다 채워져도 되긴 함, 완전 이진 트리 중, 포화 이진 트리가 있다.)

그리고 이진 트리는 일차원 배열로 표현할 수 있다.

          1

       2       3

    4        6

Null 1 2 3 4 null 6

 

이 경우, 인덱스 표를 만들면

인덱스 표	인덱스
루트 노드	1
노드 i의 부모	i / 2
노드 i의 왼쪽 자식	i * 2
노드 i의 오른쪽 자식	i * 2 + 1

이진 트리를 일차원 배열로 표현하면 배열의 한계 (삽입, 삭제 시, 데이터를 밀거나 당겨오는 작업)를

극복하지 못한다. 그래서 같은 레벨의 노드를 볼 수 있게, left와 right를 가진다.

 

이진 트리의 응용방법으로는

• 힙
• B-Tree(DB, File System에서 활용)
• 이진 탐색 트리 (Binary Search Tree)
• AVL 트리

등이 있다.

 

이진 트리의 기본 연산으로는

• 트리에 데이터 삽입
• 데이터 삭제
• 데이터 검색
• ***트리 검색***

이 트리 탐색 방법이 여러가지 있어서 정리해보려 한다.

 

 

2. 트리 탐색 방법

탐색방법은 3가지가 있다.

1. 전위 탐색 pre-order

2. 중위 탐색 in-order

3. 후위 탐색 post-order

 

              A

       B           C

    D   E     F    G

     H        I  J     K

배열로 하면 A, B, C, D, E, F, G, null, H, null, null, I, J, null, K 라는 트리가 있다 치자

 

전위 탐색 pre-order

1. Root 노드 방문

2. 왼쪽 서브 트리를 pre-order(재귀 호출로 탐색)

3. 오른쪽 서브 트리를 pre-order

 

모든 탐색은 루트부터 시작한다. A에서 루트를 방문하니 시작은 A다. 

왼쪽 서브 트리인 B로 가서, 서브 트리 기준으로 Root인 B를 방문한다. A - B

B를 기준으로 왼쪽 서브트리인 D로 가서 서브 트리 기준으로 Root인 D를 방문, A - B - D

D를 기준으로 왼쪽 서브트리가 없으니 오른쪽 서브트리를 본다. H에서 Root인 H 방문, A - B - D - H

H는 왼쪽, 오른쪽 둘 다 서브트리가 없으니 H를 끝내고 D로 돌아간다.

D도 왼쪽 오른쪽 다 뒤져봤으니 끝내고 B로 돌아간다.

B를 기준으로 오른쪽은 안뒤져봤으니 오른쪽인 E로 간다. E에서 루트인 E 방문, A - B - D - H - E

 

이런 과정을 끝까지 반복하면 순서는

A - B - D - H - E - C - F - I - J - G - K 가 된다.

 

 

중위 탐색 in-order

1. 왼쪽 서브 트리를 in-order

2. Root 노드 방문

3. 오른쪽 서브 트리를 in-order

 

루트인 A를 기준으로 왼쪽 서브트리로 들어간다. B를 기준으로 왼쪽 서브트리로 들어간다 D를 기준으로 왼쪽 서브
트리가 없으니, 루트인 D를 방문하고, 시작은 D다.

D를 기준으로 오른쪽 서브트리로 들어가니 H로 가고, H에 왼쪽 서브트리가 없으니 H를 방문한다. D - H

H의 오른쪽도 없으니 끝내고 D로 돌아간다 D는 오른쪽도 뒤져봤으니 끝낸다. B는 왼쪽을 뒤져봤으니 B를 방문한다.

D - H - B

B를 기준으로 오른쪽으로 간다. E는 왼쪽이 없으니 E를 방문한다. D - H - B - E

E는 오른쪽도 없으니 종료하고 B로 간다. B도 오른쪽까지 뒤져봤으니 A로 돌아가고, 루트인 A를 방문한다.

D - H - B - E - A

 

이런 과정을 끝까지 반복하면 순서는

D - H - B - E - A - I - F - J - C - G - K 가 된다.

 

 

후위 탐색 post-order

1. 왼쪽 서브 트리를 post-order

2. 오른쪽 서브 트리를 post-order

3. Root 노드 방문

 

A를 기준으로 왼쪽을 뒤져서 B로 간다. B를 기준으로 왼쪽을 뒤져서 D로 간다. D는 왼쪽에 아무것도 없고,

오른쪽에 H가 있다. H로 가서 왼쪽 오른쪽 다 뒤져봐도 아무것도 없으니 자신을 방문한다. H - 

H가 끝났으니 D로 돌아가고, D는 왼쪽 오른쪽 다 뒤져봤으니 자신을 방문한다. H - D

D가 마무리 되고 B로 돌아가면 B의 오른쪽인 E로 방문한다. E도 오른쪽 왼쪽 다 뒤져보고 E를 방문한다. H - D - E

E가 끝났으니 B로 돌아가고, B도 왼쪽 오른쪽 다 뒤졌으니 자신을 방문한다. H - D - E - B

B도 끝났으니 A로 돌아가고, A의 오른쪽인 C로 간다. C의 왼쪽인 F로 가고, F는 왼쪽인 I로 가고, I는 왼쪽 오른쪽

다 뒤져봐도 아무것도 안나오니 자신을 방문한다. H - D - E - B - I

 

이런 과정을 끝까지 반복하면 순서는

H - D - E - B - I - J - F - K - G - C - A 가 된다.

 

루트인 A를 기준으로 본다면

pre-order : A - B - D - H - E - C - F - I - J -G -K

in-order : D - H - B - E - A - I - F - J - C - G - K

post-order : H - D - E - B - I - J - F - K - G - C - A

 

이름 그대로 전위 탐색은 A가 가장 먼저, 중위 탐색은 A가 중간에, 후위 탐색은 A가 마지막에 탐색된다.