[자료구조] 트리(Tree)

 

트리(Tree)
 - 계층적 관계를 표현하는 비선형 자료구조.
　상위·하위로 나뉘거나 포함하는 관계일 시 계층구조로 표현.

 

---

 

자료가 저장된 노드 Node와 이 노드는 잇는 간선 Edge로 구성

 

 

• 루트 노드 Root node: 최상위에 있는 노드
• 단말 노드 Leaf node, Terminal node: 하위 노드가 없는 노드
• 내부 노드 Internal node: 단말 노드가 아닌 (하위 노드가 있는) 노드
• 형제 노드 Sibling node: 같은 부모 노드를 가지는 노드

• 레벨 Level: 루트 0레벨부터 아래로 내려갈수록 값 증가
• 크기 Size: 본인을 포함하여 자손 노드의 수
• 깊이 Depth: 해당 노드부터 루트까지 간선의 수
• 높이 Height: 최하 리프에서 루트까지 깊이 = 최대 레벨의 크기와 동일

 

서브 트리도 또 다른 서브 트리를 가질 수 있어, 보통 트리는 '재귀적 구조'로 이루어져 있다.

 

---

1. 종류

　① 이진 트리 Binary Tree

루트 노드를 중심으로 두 서브 트리로 나뉜 것. 서브 트리도 모두 이진 트리 형태로 되어 있다.

공집합 노드 Empty node
 - 이진트리에서 노드가 올 수 있는 자리에 노드가 없는 경우 공집합이라고 한다.

 

　② 전 이진 트리 Full Binary Tree

모든 노드의 자식이 0개 이거나 2개를 갖는 이진 트리

 

　③ 완전 이진 트리 Complete Binary Tree

위에서 아래로 내려오면서 왼쪽에서부터 꽉 찬 이진 트리

 

　④ 포화 이진 트리 Perfect Binary Tree

모든 레벨에 노드가 꽉 찬 이진 트리

 

　⑤ 편향 이진 트리 Skewed Binary Tree

모든 노드가 자식을 1개 가지고 있고, 한쪽 방향으로 치우쳐져 있는 트리

 

　⑥ 밸런스 Balanced
　　⑴ red-black tree
　　⑵ AVL tree

하위 노드의 좌우가 치우지지 않고 균일한 트리. 양쪽 하위 노드의 깊이 차이가 크지 않아야 한다.
균형 이진 트리는 특징에 따라 여러 종류가 있다. 

 

---

 

2. 순회 방법

　① 전위 순회 D L R

중앙을 먼저 출력한 뒤, 왼쪽 하위 노드로 이동하고 오른쪽 하위 노드로 제일 마지막에 이동하는 방법
중앙의 노드를 먼저(前) 출력해 '전위 순회'

 

　② 중위 순회 L D R

왼쪽 자식 노드를 먼저 방문하고 부모 노드를 방문한 뒤, 오른쪽 자식 노드로 내려간다.

1. 왼쪽 자식 노드 방문
2. 최하위 노드까지 모두 방문
3. 부모 노드로 올라와 출력
4. 오른쪽 자식 노드를 방문
5. 오른쪽 자식 노드도 또 다른 서브 트리의 하나의 부모
6. 오른쪽 최하위 노드를 방문할 때까지 1-5 반복

오른쪽 하위 노드 방문 시, 바로 노드를 출력하지 않고 또 다른 하위 노드가 있는지 탐색해야 한다.

 

　③ 후위 순회 L R D

루트를 가장 마지막에 출력하는 것이 특징이다.
왼쪽 하위 노드부터 시작해 상위 노드로 올라오는 건 중위 순회와 비슷
하지만 오른쪽 하위 노드까지 모든 자식을 방문해야 부모 노드를 출력할 수 있다.

 

같은 트리를 이용했어도, 어떤 순회를 선택하는가에 따라 방문 순서가 달라진다.