자료구조 - 트리

트리의 구조와 관련 용어

 

트리는 아래의 사진과 같이 노드(node)와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결된다.

 

 

루트  : 트리의 가장 위쪽에 있는 노드를 루트라고 한다. 루트는 트리 하나에 1개만 존재한다. 

 

리프 : 가장 아래쪽에 있는 노드를 의미한다. 단말 노드(terminal node), 외부 노드(external node)라고도 한다. 물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다.

 

비단말 노드(non-terminal node) : 리프를 제외한 노드. 내부 노드(internal node)라고도 한다.

 

자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다.

 

부모 : 노드와 가지가 연결되었을 때 가장 위쪽에 있는 노드. 노드의 부모는 하나뿐이다. 

 

형제 : 부모가 같은 노드

 

조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드

 

자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드

 

레벨 : 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 척도. 가장 위쪽에 있는 루트의 레벨은 0

 

차수(degree) : 각 노드가 갖는 자식의 수. 위 그림의 노드 X의 degree는 2이다. 만약 모든 노드의 자식이 2개 이하면 이진트리다.

 

높이 : 루트에서 가장 멀리 있는 리프까지의 거리. 곧 리프 레벨의 최댓값.

 

서브트리 : 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리를 subtree라고 한다.  

 

빈 트리 : 노드와 가지가 전혀 없는 트리. None tree / Null tree

---

 

순서 트리와 무순서 트리

 

트리는 형제 노드의 순서 관계가 있는지에 따라 순서 트리(ordered tree)와 무순서 트리(unordered tree)로 구분된다. 

순서 트리의 노드를 검색하는 방법은 크게 2가지이다.

 

 

너비 우선 검색 (breadth-first search)

 

너비 우선 검색은 폭 우선 검색, 가로 검색, 수형 검색이라고도 한다. 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법이다.

검색 순서 : A - B - C - D - E - F - G - H - I - J - K - L

 

 

깊이 우선 검색 (depth-first search)

 

깊이 우선 검색은 세로 검색, 수직 검색이라고도 한다. 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 한다. 리프에 도달해서 더 이상 검색할 곳이 없으면 일반 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.

 

스캔 과정에서 노드 A를 총 3번 지나간다.

-  A에서 B로 내려가기 직전에 1번

-  B에서 C로 지나가는 도중에 1번

-  C에서 A로 돌아올 때 1번

 

다른 노드에서도 마찬가지다. 두 자식 가운데 하나 또는 둘 다 없으면 노드를 지나가는 횟수는 줄어들지만, 각 노드를 최대 3번 지나간다. 이때 어느 시점에 실제로 노드를 방문하는지에 따라 깊이 우선 검색은 세 종류의 스캔 방법으로 구분한다.

 

- 전위 순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식 (A - B - D - H - E - I - J - C - F - K - L - G)- 중위 순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식 (H - D - B - I - E - J - A - K - F - L - C - H)- 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문 (H - D - I - J - E - B - K - L - F - G - C - A)