트리(Tree) 자료구조란?
1. 트리(Tree) 의 개념
- 트리는, 노드로 이루어진 자료구조로 비선형 자료구조이다.
cf) 선형 자료구조 : 스택, 큐
- 트리는 계층적 관계를 표현하는 자료구조이다.
2. 트리의 특징
1) 트리는 하나의 루트 노드를 갖는다.
2) 루트 노드는 0개 이상의 자식 노드를 갖는다.
3) 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
4) 노드(Node)와, 노드들을 연결하는 간선(Edge) 들로 구성되어 있다.
3. 트리 자료구조 성립 조건
1) 트리에는 '사이클(Cycle)이 존재할 수 없다'
- 이때, 사이클(Cycle) 이란, 시작 노드에서 출발해 -> 다른 노드를 거쳐 -> 다시 시작 노드로 돌아올 때 사이클이 존재한다고 한다.
- 트리는 사이클이 없는 하나의 연결 그래프라고 할 수 있다.
2) 트리의 노드는 Self - loop 가 존재해서는 안 된다.
- 트리는, 단순 순환 구조를 갖지 않는 무방향 그래프 구조이다.
3) N 개의 노드를 갖는 트리는, 항상 N -1 개의 간선(Edge)를 갖는다.
4) 모든 자식 노드는 한 개의 부모 노드만을 갖는다.
- 아래의 경우는,루트 노드가 2개(2, 8)가 있으므로 트리가 아닌 것이다.
트리(Tree) 관련 용어
| 용어 | 설명 |
| 루트 노드(root node) | 부모 노드가 존재하지 않는 노드로, 트리는 단 하나의 루트 노드를 가진다. |
| 단말 노드(leaf node) | 자식 노드가 없는 노드 Ex) E, F, G, H, I, J |
| 내부 노드(internal node) | 단말 노드가 아닌 노드 Ex) A, B, C, D |
| 간선(edge) | 노드를 연결하는 선 |
| 형제(sibling) | 같은 부모 노드를 갖는 노드들 Ex) E - F, H - I - J |
| 노드의 깊이(depth) | 루트 노드에서 -> 어떤 노드에 도달하기 위해 '거쳐야 하는 간선의 수' Ex) G 의 depth = 2 |
| 노드의 레벨(level) | 트리의 특정 깊이를 가지는 노드의 집합 Ex) level 2 = {B, C, D} |
| 노드의 차수(degree) | 자식 노드의 개수 Ex) B 의 degree = 2( E, F ) , C 의 degree = 1( G ) |
| 트리의 차수(degree of tree) | 트리의 최대 차수(특정 노드가 하위(자식) 노드와 연결된 개수) Ex) 위의 그림에서, 트리의 차수는 3 |
트리(Tree)의 종류
1. 이진 트리(Binary Tree)
(1) 이진 트리의 개념
1) 이진 트리는 각 노드가 '최대 두 개의 자식' 을 갖는 트리를 의미한다.
- 즉, 각 노드는 자식(서브 트리)이 없거나, 혹은 한 개 ~ 2개까지만 갖는 것이다.
2) 이때, 이진 트리에서는 서브 트리간의 '순서가 존재' 해 -> '왼쪽 서브 트리' 와 '오른쪽 서브 트리' 가 구별된다.
(2) 이진 트리와 일반 트리의 차이점
| 이진 트리 | 일반 트리 | |
| 자식 노드의 개수 | 2개 이하 | 무관 |
| 노드의 개수 | 하나도 갖지 않을 수 있음 | 1개 이상 |
| 서브 트리 간 순서 | 존재 | 존재 X |
(3) 이진 트리의 특징 및 성질
1) n 개의 노드를 가지는 이진 트리는 n - 1 개의 간선을 가진다.
2) 높이가 h 인 이진 트리의 경우, (최소 h 개)의 ~ (최대 2 ^ h-1 개)의 노드를 가진다.
3) n 개의 노드를 가지는 이진 트리의 높이는, (최대 n) or (최소 log2(n+1)) 이다.
(4) 이진 트리의 순회
- 이진 트리는 너비 우선 탐색(BFS) + 깊이 우선 탐색(DFS, [전위 순회, 중위 순회, 후위 순회]) 를 통해 순회 가능하다.
1) 너비 우선 탐색(BFS)
- 레벨 순으로, 차례대로 탐색
- 아래 그림 예시에서, 다음 순서대로 탐색이 이루어지는 것이다.
| A > B > C > D > E > F > G > H > I > J |
2) 깊이 우선 탐색(DFS)
- 전위 순회(pre-order traversal), 중위 순회(in-order traversal), 후위 순회(post-order traversal) 의 3가지 종류가 존재한다.
- 왼쪽 자식 노드 -> 오른쪽 자식 노드(B > C)로 순회하는 상황에서, 현재 노드인 A 가 방문되는 순서로 구분할 수 있다.
| 전위 순회 | 중위 순회 | 후위 순회 |
| 현재 노드(A)가 첫번째 방문 | 현재 노드(A)가 중간에 방문 | 현재 노드(A)가 마지막에 방문 |
| A > B > C (B > C 는 고정이므로) | B > A > C | B > C > A |
- 서브 트리가 존재할 때의 순회를 살펴보면, 아래 그림에서는 서브 트리가 [ B , D, E ] 이고
[Step 1] 서브 트리를 '하나의 노드(B')로 치환' 하여 전위 순회 진행
A > B' > C
[Step 2] 하나의 트리 B' 내에서, 내부적으로 순회 진행
B > D > E
[Step 3] 서브 트리의 순회 결과를 치환한 노드 B' 에 반영
A > B > D > E > C
2. 완전 이진 트리와 포화 이진 트리, 전 이진 트리
(1) 완전 이진 트리(Complete Binary Tree)
1) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
2) 이때, 마지막 레벨은 완전히 차 있지 않아도 되지만, 노드가 '왼쪽에서 -> 오른쪽으로' 먼저 채워져야 한다.
3) 마지막 레벨 i 에서, 1 ~ (2 * i - 1) 개의 노드를 가질 수 있다.
4) 완전 이진 트리는, 배열을 사용해 표현 가능하다.
(2) 포화 이진 트리(Perfect Binary Tree)
1) 포화 이진 트리는 모든 레벨이 노드로 가득 차 있는 트리이다.
2) 전 이진트리의 성질을 만족해야 한다.
3) 모든 말단 노드가 '동일한 깊이 or 레벨'을 갖는다.
4) 트리의 노드 개수 = [2^k-1 개] 이며, 이때 k 는 트리의 높이이다.
(3) 전 이진 트리(Full Binary Tree)
- 전 이진 트리는 모든 노드가 0개 or 2개의 자식 노드를 갖는 트리이다.
3. 이진 탐색 트리(Binary Search Tree)
- 이진 탐색 트리는, 이진 트리 + 아래의 속성을 만족하는 순서화된 이진 트리로,
1) 이진 탐색 트리의 노드에 저장된 키(Key)는 '유일' 하다.
2) 부모의 키가 > 왼쪽 자식의 키보다 크고
3) 부모의 키가 < 오른쪽 자식 노드의 키보다 작다.
4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리에 해당된다.
- 참고 : https://code-lab1.tistory.com/10
4. 편향 트리(Skew Tree)
- 모든 노드들이 자식을 하나만 가지는 트리로,
- Left Skew Tree : 왼쪽 방향으로 자식을 하나만 가지는 경우
- Right Skew Tree : 오른쪽 방향으로 자식을 하나만 가지는 경우
+ 자식을 하나씩만 가지는데, 왼쪽 오른쪽을 나눌 필요가 있나..?
5. m 원 탐색 트리(m-way Search Tree)
- 최대 m 개의 서브 트리를 갖는 탐색 트리
- 이진 탐색 트리의 확장된 형태로, 높이를 줄이기 위해 사용
6. 균형 트리(Balanced Tree, B-Tree)
- m 원 탐색 트리에서 높이 균형을 유지하는 트리
- height - balanced m-way Tree 라고도 한다.
참고
- https://mommoo.tistory.com/95
- https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14
- https://code-lab1.tistory.com/8
- https://yoongrammer.tistory.com/68
'Programming > Algorithm' 카테고리의 다른 글
| [Algorithm] 비트마스킹(Bit Masking) (0) | 2022.06.25 |
|---|---|
| [Algorithm] 프로그래머스 전화번호 목록(해시) (0) | 2022.05.13 |
| [Algorithm] 백트래킹(Backtracking) (0) | 2022.02.27 |
| [Data Structure] 힙(Heap) 연산 (0) | 2022.02.21 |
| [Algorithm] DP(Dynamic Programming) (0) | 2022.01.15 |
