[Data Structure] 트리 자료구조 (Tree Data Structure)

트리 자료구조 (Tree Data Structure)

출처:  https://discuss.boardinfinity.com/t/what-is-a-tree-data-structure/12236

 

---

트리: 노드(node)로 이루어진 자료구조

• 트리의 루트 노드는 오직 한 개
• 루트는 0개 이상의 자식 노드를 갖고 있음
• 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있으며 이 정의가 반복됨

트리의 구성 요소

• 노드, 루트 노드, 부모 노드, 자식 노드, 형제 노드, 간선, 잎 노드(단말 노드, 외부 노드), 가지 노드(비 단말 노드, 내부 노드)

노드(node)

• 트리를 구성하고 있는 각각의 요소 → 위 그림에서 P, Q, A, B, L, E, F, G, R, C, D, M, H, I 각각의 요소

루트 노드(root node)

• 최상위 노드 → 위 그림에서는 P

부모 노드(parent node)

• 자식을 가진 노드 → 위 그림에서 P는 Q와 R의 부모 노드, L은 E, F, G의 부모 노드

자식 노드(child node)

• 부모 노드의 하위 노드들 → 위 그림에서 Q와 R은 P의 자식 노드

형제 노드(sibling node)

• 부모가 같은 자식 노드 → 위 그림에서 E, F, G는 부모 노드가 L로 동일함 → E, F, G는 부모가 같은 형제 노드

간선(edge, branch, link)

• 노드를 연결하는 선 → 그림 상 노드와 노드를 연결해주는 직선

잎 노드(leaf node) = 외부 노드(external node) = 단말 노드(terminal node)

• 자식이 더 이상 없는 노드 → 위 그림에서는 B, D, E, F, G, H, I

가지 노드(branch node) = 내부 노드(internal node) = 비 단말 노드(non-terminal node)

• 하나 이상의 자식 노드를 갖는 노드 → 위 그림에서는 P, Q, R, A, C, M, L

 

추가적으로 알아야 할 기본 용어

• 노드의 크기, 노드의 깊이, 노드의 레벨, 노드의 차수, 트리의 차수, 트리의 레벨

출처:  https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

 

노드의 크기(size)

• 1 (self) + 모든 자손 노드의 수 → 위 그림에서 P는 size가 14(자기 자신 + 13), M은 3(자기 자신 + 2)
  • 루트 노드의 경우 전체 노드의 갯수

노드의 깊이(depth)

• 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 → 0부터 선을 몇번 거쳐가야 하는지 / 그림 참고

노드의 레벨(level)

• 루트에서 어떤 노드까지 간선의 수 → 루트 노드는 level 0, 그 하위 노드는 level1, …, level n까지

노드의 차수(degree)

• 특정 노드의 자식 수 → 맨 위 그림에서 잎 노드의 차수는 0(자식이 없기 때문에), P 노드의 차수는 2(자식이 Q노드, R노드 2개이므로)

트리의 차수(degree of tree)

• 트리의 최대 차수 → 위 그림에서는 최대 차수가 L일 때 3이므로, 트리의 차수는 3이다.
• n차 방정식을 나타낼 때, y=x²+401x+5일 때, 최대 차수를 2로 보는 것과 동일

트리의 높이(height)

• 루트 노드로부터 가장 깊이 있는 노드의 깊이(거쳐야 하는 간선의 수) → 위 그림에서는 5(P→Q→A→L→[E or F or G]

 

트리의 특징

1. 트리는 반드시 1개의 루트 노드와 0개 이상의 하위 노드를 가짐
2. 데이터를 순차적으로 저장하지 않으므로 비선형 자료구조
3. 트리내에서 또 다른 트리가 있는 재귀적 자료구조
4. 간선의 수 = 전체 노드 수 - 1 → 맨 위 그림에서 총 노드 수는 14개이므로 간선의 수는 14-1 = 13이다.
5. 노드 간에 부모-자식 관계를 갖고 있는 계층형 자료구조, 모든 자식 노드는 하나의 부모 노드만 가짐
6. 노드들끼리는 서로 연결되지 않음 → 서로 연결되면 단순 순환(loop)를 가짐 but 트리는 무방향 그래프 구조

 

트리가 아닌 경우

1) 루트 노드가 1개가 아닌 경우

출처:  https://www.geeksforgeeks.org/count-number-non-reachable-nodes/

 

위는 루트 노드가 2개(0과 3)가 있으므로 트리가 될 수 없음

 

2) 노드가 부모-자식 관계가 아닌데 연결된 경우

• 왼쪽의 경우 1↔2, 3↔4가 연결되어 있고, 루트 노드(1, 2)가 2개이므로 트리가 아님
• 오른쪽의 경우 6↔7이 연결되어 있으므로 트리가 아님

 

트리의 종류

편향 이진트리(Skewed Binary Tree), 이진트리(Binary Tree), 이진 탐색 트리(Binary Search Tree:BST), 포화 이진트리(Full Binary Tree), 완전 이진트리(Complete Binary Tree)

1. 편향 이진트리(경사 트리, Skewed Binary Tree)

출처:  https://www.google.com/url?sa=i&url=https%3A%2F%2Fstackoverflow.com%2Fquestions%2F28315718%2Fskewed-trees-relation-to-binary-search-tree&psig=AOvVaw2y_BWZ7sfpF1RXlEUtSJz6&ust=1682745314392000&source=images&cd=vfe&ved=0CBEQjRxqFwoTCNDtqvfoy_4CFQAAAAAdAAAAABAE

• 한 쪽으로만 치우친 트리

 

2. 이진트리(Binary Tree)

출처:  https://www.google.com/url?sa=i&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBinary_tree&psig=AOvVaw0wWUxkFlm_n-dA9OEUFbPv&ust=1682745277910000&source=images&cd=vfe&ved=0CBEQjRxqFwoTCIiWheboy_4CFQAAAAAdAAAAABAE

“한 부모 노드에 자식은 2개 이하”

• 각 노드의 차수가 2 이하인 트리

 

3. 이진 탐색 트리(Binary Search Tree:BST)

출처: https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.javatpoint.com%2Fbinary-search-tree&psig=AOvVaw2KpxQzmvfXcFbst8U9_Qwf&ust=1682745331169000&source=images&cd=vfe&ved=0CBEQjRxqFwoTCJjhuP_oy_4CFQAAAAAdAAAAABAE

“왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다”

• 이진 탐색을 위한 이진트리(정렬되어 있어야 함)

 

4. 포화 이진트리(Full Binary Tree) vs 완전 이진트리(Complete Binary Tree)

1. 포화 이진트리: 잎 노드를 제외하고 모든 노드들의 차수가 2이며, 잎 노드는 자식을 가지지 않는 트리
2. 완전 이진트리: 높이가 h일 때 레벨 1부터 h-1까지는 포화 이진트리이고, 레벨 h에서는 왼쪽부터 노드가 채워져 있는 트리

• 마지막 레벨을 제외한 모든 레벨에서 노드가 가득 차 있음
• 마지막 레벨에서는 노드가 왼쪽부터 순서대로 채워져 있음

→ 포화 이진 트리의 경우에는 모든 레벨에서 노드가 꽉 차 있는 반면, 완전 이진 트리의 경우에는 마지막 레벨을 제외하고 모든 레벨에서 노드가 꽉 차 있고, 마지막 레벨에서는 왼쪽부터 순서대로 채워져 있음

따라서, 포화 이진트리는 항상 완전 이진트리이지만, 모든 완전 이진트리가 포화 이진트리는 아니다.

 

일반 트리에서 이진트리로 변환(Conversion of a general tree to binary tree)

참고 + 출처:  https://www.geeksforgeeks.org/convert-a-generic-treen-array-tree-to-binary-tree/

• 일반 트리는 차수가 불규칙적이기 때문에 자료 처리할 때 비효율적임 → 이럴 해결하기 위해 이진 트리로 변환해야 하는 상황이 생김

Algorithm

Step 1. 각 부모 노드 당 2개의 노드만 갖도록 부모 노드의 왼쪽 자식과 오른쪽 형제 노드를 연결한다.

Step 2. 다음 적절한 각도로 회전시킨다. (일반적으로 45도 회전)

Step 3. 회전한 트리를 적절하게 재배치하면 이진 트리가 됨