[자료구조] 트리(tree)

1. 트리(Tree)

1) 개념

• 그래프의 일종으로, 회로가 없고 서로 다른 노드를 잇는 길이 하나뿐인 그래프를 트리라고 한다.
• 비선형 계층적 자료구조

2) 특징

• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 트리의 하나의 노드에서 다른 노드로 가는 경로는 유일하다. (중복 방문 하지않는 조건)

3) 용어

• 노드(node) : 트리를 구성하고 있는 기본 요소
• 간선(edge) : 노드와 노드 간의 연결선
• 루트(root) : 부모가 없는 최상위 노드
• 부모(parent) : 부속트리(sub-tree)를 가진 노드
• 자식(child) : 부모에 속하는 부속노드
• 형제(siblings) : 부모가 같은 자식노드들
• 조상(ancestor) : 노드의 부모노드들
• 자손(descendant) : 노드의 부속트리에 있는 모든 노드들
• 맆(leaf, 단말, terminal) 노드 : 차수가 0인 노드로 트리의 맨 끝에 달린 노드
• 내부(internal, non-terminal) 노드 : 차수가 1이상인 노드

---

• 노드의 깊이(depth) : 루트노드에서 자신까지 가는 경로의 길 (루트노드의 깊이 0)
• 노드의 레벨(level) : 루트노드에서 자신까지 가는 경로의 길이 + 1 (루트노드의 레벨 1)
• 노드의 높이(height) : 그 노드와 단말노드 사이의 경로의 최대 길이
• 노드의 크기(size) : 자기 자신 및 모든 자손노드의 수
• 노드의 차수(degree) : 노드의 부속트리의 개수

---

• 트리의 깊이(Depth of tree) : 트리에 속한 노드의 최대 레벨
• 트리의 차수(degree of tree) : 트리의 최대 차수

예시)

2. 이진트리(Binary Tree)

1) 개념

• 각각의 노드는 최대 2개의 자식노드를 가진다.
• 이진탐색트리와 이진 힙 구현에 사용된다.
• 효율적인 검색과 정렬을 위해 사용된다.

2) 특징

• 노드가 없는 트리(Empty Node)도 이진트리가 된다.
• 부속트리(자식노드)에 순서가 있다.
• 이진트리의 최대 레벨이 h인 경우 트리의 최대 노드의 개수는 $2^h-1$ 이다.
• 노드가 N개 일때, 시간복잡도는 $O(log_{2}N)$ 이다.
• 최악의 경우, $O(N)$ 이다.

3) 종류

정 이진트리(Full Binary Tree)

모든 노드가 0개 또는 2개의 자식노드를 갖는다. 자식을 하나만 가진 노드가 없어야한다. 포화 이진트리에 속함.

포화 이진트리(Perfect Binary Tree)

모든 내부노드가 두 개의 자식노드를 가지며 모든 맆노드가 똑같은 레벨에 있다. 완벽한 피라미드 모양.

완전 이진트리(Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있다. 마지막 레벨은 왼쪽부터 채워져있고 꽉 차있을 필요는 없다.