자료구조 - 트리(tree)

BFS와 DFS에 대해서 알아보기 이전에 먼저, 트리라는 자료 구조에 대해 알 필요가 있다.

아래의 내용은 이지스퍼블리싱의 Do it! 자료구조와 함께 배우는 알고리즘입문 책을 참고하여 재구성하였다.

 

트리(tree)

---

데이터 사이의 계층 관계를 나타내는 자료 구조이다.

트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지를 통해 다른 노드와 연결되어 있다.

 

트리 관련 용어

트리(tree)

• 루트(root): 트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 한다. 하나의 트리에는 하나의 루트가 있다.
• 리프(leaf): 트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라고 한다. 이때 '가장 아랫부분에 위치한다'라는 말은 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라 더 이상 뻗어나갈 수 없는 마지막에 노드가 위치한다는 의미이다.
• 안쪽노드(none-terminal node): 루트를 포함하여 리프를 제외한 노드를 안쪽 노드라고 한다.
• 자식(child): 어떤 노드로부터 가지로 연결된 아래쪽 노드를 자식(child)라고 한다. 노드는 자식을 여러개 가질 수 있다.
• 부모(parent): 어떤 노드에서 가지로 연결된 위쪽 노드를 부모(parent)라고 한다. 노드는 1개의 부모를 가진다. *루트는 부모를 가질 수 없다.
• 형제(sibling): 같은 부모를 가지는 노드를 형제(sibling)이라고 한다.
• 조상(ancestor): 어떤 노드에서 가지로 연결된 위쪽 노드 모두를 조상(ancestor)이라고 한다.
• 자손(descendant): 어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손(descendant)라고 한다.
• 레벨(level): 루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨(level)이라고 한다. 루트의 레벨은 0이고 루트로부터 가지가 하나씩 아래로 뻗어 나갈때 마다 레벨이 1씩 늘어난다.
• 차수(degree): 노드가 갖는 자식의 수를 차수(degree)라고 한다. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다.
• 높이(height): 루트로부터 가장 머리 떨어진 리프까지의 거리(리프 레벨의 최댓값)를 높이(height)이라고 한다.
• 서브트리(subtree): 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브 트리(subtree)라고 한다.
• 널트리(null tree): 노드, 가지가 없는 트리를 널 트리(null tree)라고 한다.
• 순서트리와 무순서 트리: 형제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류 한다. 형제 노드의 순서를 따지면 순서트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)라고 한다.

 

순서트리의 탐색

순서트리의 노드를 스캔하는 방법은 두 가지이다. 이진 트리를 예로 들어 살펴보자.

 

- 너비우선 탐색(Breadth-First Search): 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고, 한 레벨의 검색이 끝나면 다음 레벨로 넘어간다.

너비우선탐색(BFS)

- 깊이 우선 탐색(Depth-First Search): 루트에서 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다. 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게로 돌아간다. 그런 다음 다시 자식 노드로 내려간다. 이 과정을 처음 시작한 루트에게로 다시 돌아갈때까지 반복한다.

깊이우선탐색(DFS)

 

만약 깊이 우선 탐색을 진행하면 어떤 노드에 대해 언제 방문 할지를 다음과 같이 세 종류로 구분할 수 있다.

- 전위 순회(Preorder): 노드 방문 → 왼쪽 자식 → 오른쪽 자식

노드 A를 지나가는 경우: A → B → C
전위 순회로 DFS: A → B → D → H → E → I →J → C → F → K → L →G

- 중위 순회(Inorder): 왼쪽 자식 → 노드 방문 → 오른쪽 자식

노드 A를 지나가는 경우: B → A → C
중위 순회로 DFS: H → D → B → I→ E → J → A → K → F  → L → C → G

- 후위 순회(Postorder):왼쪽자식 → 오른쪽 자식 → 노드 방문

노드 A를 지나가는 경우: B → C → A
후위 순회로 DFS: H → D  → I  → J  → E  → B → K → L  → F  → G → C → A