트리

지난 글 : [알고리즘/Do it 알고리즘] - 원형 이중 연결 리스트 만들기

 

지난 4일간 살펴본 리스트는 순서대로 데이터를 나열하는 자료구조다. 이제 배울 자료구조는 데이터 사이의 계층 관계를 나타내는 트리다.

 

트리 알아보기

트리(tree)와 트리 관련 용어를 알아보자. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지로 연결되어 있다.

 

루트 

트리의 가장 윗부분에 위치하는 노드를 루트(root)라 한다. 하나의 트리에는 하나의 루트만 있다. 

 

리프

트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라 한다. 이때 '가장 아래에 위치한다'는 말은 물리적으로 가장 아랫부분에 위치한다는 것이 아닌 노드가 더 이상 뻗어 나가지 않는 마지막에 위치한다는 의미다. (리프를 끝 노드(terminal node) 또는 바깥 노드(external node)라고도 한다.)

 

안쪽 노드

리프를 제외한 나머지 노드(루트 포함)를 안쪽 노드라 한다. (안쪽 노드를 끝이 아닌 노드(non - terminal node)라고도 한다.)

 

자식

어떤 노드에서 가지로 연결된 아래쪽 노드를 자식(child)이라 한다. 노드는 자식을 여럿 가질 수 있다. 

 

부모

어떤 노드에서 가지로 연결된 바로 위쪽 노드를 부모(parent)라 한다. 각 노드에서 부모는 하나뿐이다. (루트는 부모를 가질 수 없다.)

 

형제

부모가 같은 노드를 형제(sibling)라 한다.

 

조상 

어떤 노드에서 위쪽으로 뻗어 나간 모든 노드를 조상(ancestor)이라 한다.

 

자손

어떤 노드에서 아래쪽으로 뻗어 나간 모든 노드를 자손(descendant)이라 한다.

 

레벨

루트로부터 얼마나 떨어져 있는가를 나타낸 값을 레벨(level)이라 한다. 루트의 레벨은 0이고, 루트에서 가지가 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어난다.

 

차수

노드가 갖는 자식의 수를 차수(degree)라 한다. 모든 노드의 차수가 n이하인 트리를 n진 트리라 한다.

 

높이

루트에서 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)를 높이(height)라 한다. 

 

서브트리

트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브트리(subtree)라 한다.

 

널 트리

노드가 전혀 없는 트리를 널 트리(null tree)라 한다.

 

순서 트리와 무순서 트리 살펴보기

형제 노드 사이의 순서 관계를 따지는지 그렇지 않은지에 따라 트리를 두 종류로 구분한다. 형제 노드의 순서를 따지면 순서 트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)라 한다.

 

순서 트리 탐색 살펴보기

순서 트리의 노드를 스캔하는 방법은 2가지다. 여기서는 이진트리(모든 노드의 자식 수가 2개 이하인 트리)를 예로 살펴보자.

 

너비 우선 탐색(가로형 탐색)

너비 우선 탐색(breadth - first search)은 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다 한 레벨에서 탐색이 끝나면 다음 레벨로 내려간다. 

 

깊이 우선 탐색(세로형 탐색)

깊이 우선 탐색(depth - first search)은 리프에 이를 때까지 아래로 내려가며 탐색한다. 리프에 도달해 더 이상 탐색할 곳이 없으면 부모에게로 돌아간 후 다시 자식 노드로 내려간다.

 

전위 순회(preorder)

아래와 같은 순서로 깊이 우선 탐색을 진행한다.

노드 방문 → 왼쪽 자식 → 오른쪽 자식

 

중위 순회 (inorder)

아래와 같은 순서로 깊이 우선 탐색을 진행한다.

왼쪽 자식 → 노드 방문 → 오른쪽 자식

 

후위 순회(postorder)

아래와 같은 순서로 깊이 우선 탐색을 진행한다.

왼쪽 자식 → 오른쪽 자식 → (돌아와)노드 방문

 

참고 서적 :