자료구조 비선형구조 트리

자료구조는 선형 구조와 비선형 구조로 분류를 할 수 있습니다. 지난번 포스팅에서는 선형 구조인 스택, 큐, 데크, 리스트에 대해 알아보았습니다. 이번에는 비선형 구조 중 트리에 대해 알아보려고 합니다. 트리와 그래프는 사이클의 유무에 따른 차이가 있습니다. 사이클이 있는 형태를 그래프라고 하며 그래프 중 사이클이 없는 형태를 트리라고 합니다. 실생활에서 떠올려 볼 수 있는 것은 트리는 조직 관계도, 그래프는 2호선 지하철 노선도, 통신망 정도 생각해볼 수 있겠습니다.

 

 

 

트리

트리의 정의에 대해 조금 더 살펴보겠습니다. 트리는 노드와 엣지를 사용해서 사이클이 없게 구성한 그래프이며 방향이 있는 방향 그래프입니다. 위 이미지에서 A를 루트 노드라고 하며 루트 노드는 트리에서 단 하나만 존재합니다. 또한 자식 노드는 한 개의 부모 노드만 가집니다. D와 E의 부모 노드가 B이며, B는 D와 E 두 개의 자식 노드를 가지는 것입니다. 그렇기 때문에 노드가 N개인 경우 항상 N-1개의 엣지를 가집니다. 

 

1. 트리 용어

트리에서 사용하는 용어 몇 가지를 알아보겠습니다.

▶ 정점(Node) : 정점은 노드라고도 불리며 이미지 상 A, B, C, D, E, F, G를 의미합니다.

▶ 간선(Edge) : 엣지라고 불리는 간선은 각 노드를 연결한 선을 의미합니다. 링크 혹은 branch라고 불리기도 합니다. 

▶ 레벨(Level) : 루트 노드 레벨을 1로 가정했을 때 루트 노드를 기준으로 어떠한 노드까지의 길이를 의미합니다. 예를 들어 F 노드의 경우 레벨 3, C 노드의 경우 레벨 2가 되는데 자식 노드의 레벨은 부모 노드의 레벨에 1을 더한 수입니다. 

▶ 루트 노드(Root Node) : 루트 노드는 위 이미지 상 A 노드를 의미합니다. 트리의 시작점이라고 할 수 있으며, 트리에서 부모가 없는 유일한 노드입니다.

▶ 부모 노드(Parent Node) : 어떠한 노드를 기준으로 그 이전 레벨의 노드를 말합니다. D와 E의 부모 노드는 B가 됩니다.

▶ 자식 노드(Child Node) : 어떤 노드에 연결된 다음 레벨의 노드를 의미합니다. C 노드의 자식 노드는 F, G가 되며 A 노드의 자식 노드는 B와 C가 되는 것입니다.

▶ 조상 노드(Ancestor Node) : 조상 노드는 자신보다 윗 레벨에 있는 노드 중 같은 경로 상에 있는 노드를 말합니다. D의 부모 노드는 B이며 B의 부모 노드는 A가 됩니다. 여기서 D의 조상 노드는 B와 A가 되는 것입니다. 

▶ 형제 노드(Sibling) : 부모 노드가 같은 노드들을 의미합니다. 

▶ 차수(Degree) : 각 노드와 연결된 자식 노드의 수를 말하며 B노드의 차수는 2입니다. 전체 차수의 경우 각 노드의 차수 중에서 가장 큰 수를 전체 노드의 차수라고 합니다. F와 G는 둘 다 C를 부모 노드로 가집니다. 따라서 F의 형제 노드는 G가 됩니다. 

▶ 단말 노드(Leaf node) : 단말 노드는 자식 노드를 하나도 갖고 있지 않은 노드를 의미합니다. 즉, D, E, F, G 노드는 리프 노드입니다. 

▶ 비 단말 노드(Non-Terminal node) : 비 단말 노드는 단말 노드와 반대의 개념입니다. 즉 자식 노드를 하나라도 가지고 있다면 비 단말 노드라고 합니다. 이미지에서는 A, B, C가 비 단말 노드입니다. 

▶ 깊이(Depth) : 루트 노드에서 특정 노드까지 가기 위해 지나가는 간선의 수를 말합니다. B까지 가기 위해서는 1의 간선을 거치기 때문에 B의 깊이는 1이며, D까지 가기 위해서는 두 개의 간선을 거치기 때문에 D의 깊이는 2입니다. 그리고 깊이 중 가장 큰 수가 트리의 높이가 됩니다.

 

2. 트리의 순회 방법

트리를 순회하는 방법에는 전위 순회, 중위 순회, 후위 순회 이렇게 3가지가 있습니다. 

 

▶ 전위 순회(Pre-order) : 전위 순회는 Root를 가장 먼저 방문하는 순회 방법입니다. 즉 노드의 방문 순서가 Root -> Left->Right가 됩니다. 쉽게 알기 위해 위 이미지에서 B, D, E 형태만 봤을 때 루트인 B를 먼저 순회한 뒤 D, E 순서대로 노드를 순회합니다. 

▶ 중위 순회(In-order) : 중위 순회는 Left->Root->Right 순서로 순회합니다. 마찬가지로 B, D, E만 봤을 때 D->B->E 순서대로 순회하게 됩니다. 

▶ 후위 순회(Post-order) : 후위 순회는 Root를 가장 마지막에 방문합니다. 즉, Left->Right->Root 순서대로 순회합니다. B, D, E만 봤을 때에는 B->E->D 순서대로 순회합니다. 

 

3. 이진트리의 종류

트리의 종류 중 하나로 이진트리라는 것이 있습니다. 이진트리는 자식 노드가 둘 이하인 트리를 의미합니다. 위 이미지를 보면 리프 노드를 제외한 모든 노드의 자식 노드가 2개인 것을 볼 수 있습니다. 즉, 이진트리를 의미합니다.

 

▶ 포화 이진트리 : 이진트리 중에서도 위의 트리처럼 모든 레벨에서 노드가 빈 곳이 없는 트리를 포화 이진트리라고 합니다. 

▶ 완전 이진트리 : 트리의 노드도 순서가 있습니다. 위의 트리는 A, B, C, D, E, F, G의 순서를 가집니다. 완전 이진트리는 마지막 노드가 없는 트리를 의미하며 G의 노드가 없고, F 노드까지만 있는 트리였다면 완전 이진트리가 됩니다.

▶ 편향 이진트리 : 편향 이진트리는 오른쪽이나 왼쪽으로만 노드가 존재하는 트리를 말합니다. 위의 트리 모형에서 A, C, B 노드만 존재하거나 A, B, D 노드만 존재한다면 편향 이진트리가 되는 것입니다.