Study/Data Structure
[자료구조] Tree의 구조와 용어, 주요 특징
jonghne
2024. 3. 15. 12:32
Tree의 개념
트리(Tree) 란 노드(Node)들의 집합으로, 노드는 값(value)과 다른 노드들을 가리키는 레퍼런스(Reference)들로 구성되어 있습니다.
Tree의 주요 용어
간선
간선 (Edge)란 노드와 노드를 연결하는 선을 의미하고, 구현 관점에서는 노드 간의 주소 값 레퍼런스(참조)를 의미합니다.
역할 별 노드
트리의 노드는 역할에 따라 자녀 노드 , 부모 노드, 형제 노드, 조상 노드, 자손 노드, 내부 노드, 외부 노드 가 있습니다.
각 노드들이 무엇이고 어떤 역할을 하는지 그림을 통해 알아보겠습니다.
1. 루트 노드 (Root Node)
- 모든 노드의 최상위 노드
- 위 그림에서 P에 해당합니다.
2. 자녀 노드 (Child Node)
- 특정 노드의 바로 아래에 연결된 노드
- 부모 노드로 부터 직접적으로 연결된 노드
- 위 그림에서 E,F,G 노드는 L 노드의 자식 노드입니다.
3. 부모 노드 (Parent Node)
- 자녀 노드를 가지는 노드
- 위 그림에서 L 노드는 E,F,G 노드의 부모 노드입니다.
4. 형제 노드 (Parent Node)
- 같은 부모를 가지는 노드들
- 위 그림에서 A, B 노드는 Q 노드를 부모로 가지는 형제 노드입니다.
5. 조상 노드 (Ancestor Node)
- 부모 노드를 따라서 루트 노드까지 올라가며 만나는 모든 노드
- 위 그림에서 E 노드의 조상 노드는 L, A, Q, P 노드 입니다.
6. 자손 노드 (Ancestor Node)
- 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
- 위 그림에서 A의 자손 노드는 L, E, F, G 입니다.
7. 내부 노드 (Internal Node)
- 자녀 노드를 가지는 모든 노드
- 리프 노드를 제외한 모든 노드가 이에 해당합니다.
- 위 그림에서 내부 노드는 B, D, E, F, G, H, I 노드를 제외한 모든 노드가 이에 해당합니다.
8. 외부 노드 (External Node)
- 자식 노드를 가지지 않는 모든 노드
- 흔히, Leaf Node라고 부르곤 합니다.
- 위 그림에서 외부 노드는 B, D, E, F, G, H, I 노드입니다.
트리 및 노드의 경로 / 길이 / 높이
1. 경로
- 특정 노드에서 목적지 노드 까지 노드들의 순서를 의미합니다.
- 위 그림에서 P 노드에서 G 노드까지의 경로는 다음과 같습니다.
- P -> Q -> A -> L -> G
2. 경로의 길이
- 경로에 있는 노드들의 수를 의미합니다.
- 위 그림에서 P 노드에서 G 노드까지의 경로의 길이는 5입니다.
- P, Q, A, L, G 노드를 거치기 때문입니다.
3. 노드의 높이
- 특정 노드에서 리프 노드까지의 가장 긴 경로의 간선(Edge) 수
- 리프 노드의 높이는 0
- 위 그림에서 Q 노드의 높이는 가장 아래에 있는 리프 노드 까지의 간선의 수인 3입니다.
- 즉, 리프 노드 B 까지의 간선의 수가 아닌 가장 하위에 있는 리프 노드인 E,F,G 까지의 간선의 수입니다.
4. 트리의 높이
- 루트 노드의 높이
- 위 그림에서는 P 노드의 높이인 4가 트리의 높이입니다.
5. 노드의 깊이
- 루트 노드에서 특정 노드까지 경로의 간선(Edge) 수
- 루트 노드의 깊이는 0
- 노드의 높이는 리프노드가 기준이었다면, 노드의 깊이는 루트 노드가 기준입니다.
- 위 그림에서 Q 노드의 깊이는 1입니다.
6. 트리의 깊이
- 트리에 있는 노드들의 깊이 중 가장 긴 깊이(Depth)
- 위 그림에서 트리의 깊이는 리프노드의 깊이인 4입니다.
- 트리의 높이 = 트리의 깊이
차수 (degree) / 거리 (distance)
1. 노드의 차수
- 노드의 자녀 노드 수를 의미합니다.
- 위 그림에서 L의 차수는 3입니다.
2. 트리의 차수
- 트리에 있는 노드들의 차수 중 가장 큰 차수
- 위 그림에서 트리의 차수는 L 노드의 차수인 3입니다.
3. 노드 간 거리
- 두 노드 사이의 최단 경로의 간선 수
- 위 그림에서 E 노드와 P 노드의 거리는 4입니다 (E -> L -> A -> Q -> P)
노드의 레벨 / 너비(width)
1. 노드의 레벨
- 특정 노드에서 루트 노드 까지 경로의 간선의 수
- 위 그림에서 Q 노드는 루트 노드 P까지 간선의 수가 1개이기 때문에 Level 1 입니다.
- 위 그림에서 E 노드는 루트 노드 P까지 간선의 수가 4개이기 때문에 Level 4 입니다.
2. 너비 (width)
- 임의의 레벨에서 노드의 수
- 위 그림에서 Level 2의 width는 2입니다.
트리 및 노드의 크기(size)
1. 노드의 크기
- 자신을 포함한 자손 노드의 수
- 위 그림에서 A 노드의 크기는 자손 노드 L, E, F, G의 수인 4입니다.
2. 트리의 크기
- 트리의 모든의 노드 수
- 위 그림에서 트리의 크기는 13입니다.
서브 트리
- 특정 트리에서 자식 노드가 각각 루트 노드가 되어 하나의 트리를 구성하는 부분 트리를 의미합니다.
- 위 그림에서는 L 을 루트 노드로 가지는 서브트리가 존재합니다.
Tree의 주요 특징
1. 루트 노드는 하나만 존재한다.
2. 트리는 사이클이 존재하지 않는다.
3. 자녀 노드는 하나의 부모 노드만 존재한다.
4. 데이터를 순차적으로 저장하지 않는 비선형 구조이다.
- 데이터의 순서를 지키며 저장하는 ArrayList 또는 LinkedList와 다르게 데이터를 순차적으로 저장하지 않습니다.
5. 서브 트리를 가지는 재귀적 구조이다.
6. 부모-자식 관계를 가지는 계층적 구조이다.
📌 참고