트리(Tree)

개념 : 트리는 노드로 이루어진 자료구조

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

트리 특징

• 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
• 트리는 계층 모델 이다.
• 사이클이 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  • 즉, 간선은 항상 (N(정점의 개수) - 1) 만큼을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  • 임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

루트 노드 위치에 따라 분류

• Pre-order(전위 순회)
  • 루트 노드 → 왼쪽 서브 트리 → 오른쪽 서브 트리
• In-order(중위 순회)
  • 왼쪽 서브 트리 → 루트 노드 트리 → 오른쪽 서브 트리
• Post-order(후위 순회)
  • 왼쪽 서브 트리 →오른쪽 서브 트리 → 루트 노드 트리

완전 이진 트리 vs 전 이진 트리 vs 포화 이진 트리

1. 완전 이진 트리 [Complete Binary Tree]

• 또 다른 정의는 가장 오른쪽의 잎 노드가 (아마도 모두) 제거된 포화 이진 트리다.
• 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
• 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리. 즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
  

2. 전 이진 트리[Full Binary Tree]

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
  

3. 포화 이진 트리 [Perfect Binary Tree]

• 전 이진 트리이면서 완전 이진 트리인 경우
• 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.
• 모든 내부 노드가 두 개의 자식 노드를 가진다.
• 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
• 노드의 개수가 정확히 2^(k-1)개여야 한다. (k:트리의 높이)