[자료구조] 트리 (Tree)

트리 / Tree

트리(Tree) 구조는 여러 개의 노드(Node)로 구성되는 그래프의 한 종류이다. 

뿌리(Root)가 아래에 있는 일반적인 나무의 형태를 뒤집어 놓은 듯한 형태를 가진다. 

크기 6, 높이 2인 이진 트리

 

트리 성립 조건

아래의 조건을 모두 만족해야 한다.

1. 연결 그래프(Acyclic Connected Graph)
   • 모든 노드가 연결되어 있어야 하며, 분리된 노드가 존재할 수 없다.
2. 사이클(Cycle)이 없어야 함
   • 사이클이 존재하는 순환 구조를 가질 수 없다.
   • 간선(Edge)를 추가했을 때 사이클이 생긴다면 조건을 위반하게 된다.
3. 노드 개수(N)과 간선 개수(E)의 관계 : E = N - 1
   • 전체 간선의 개수는 전체 노드 개수보다 1 작다.

 

주의 사항

1. 루트 노드(Root Node)는 필수가 아니다.
   • 일반적으로 트리는 하나의 루트 노드를 가지지만 루트 노드가 필수는 아니다.
   • 대표적으로 포레스트(Forest, 독립적인 트리의 모음)가 있다. 
2. 유향 그래프(Directed Graph)에서도 트리 구조가 가능하다.
   • 위의 조건을 모두 만족시키는 DAG(Directed Acyclic Graph, 방향 비순환 그래프) 형태가 가능하다. 
3. 비계층적(Non-Hierarchical) 트리가 존재할 수 있다.
   • 일반적으로 트리는 부모-자식 관계를 가지는 계층적 구조 형태지만 그 계층성이 모호한 경우가 있다. 
   • 포레스트 구조는 특정한 계층 구조를 가지지 않을 수 있다. 
   • Union-Find, DFS 등에서 트리는 계층적 의미보다 집합을 표현하는 도구 또는 경로 등을 나타낼 수 있다. 

 

트리의 종류

• 일반 트리(General Tree)
  • 각 노드가 임의 개수의 자식 노드를 가질 수 있는 트리
• 이진 트리(Binary Tree)
  • 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리
  • 정 이진 트리, 포화 이진 트리, 완전 이진 트리, 이진 탐색 트리, 균형 이진 트리, 힙 등으로 세분화

• 트라이(Trie)
  
  • 문자열 검색을 빠르게 수행할 수 있는 트리 구조

• m-Way Tree
  • 이진 트리를 확장하여 각 노드가 2개 이상의 자식 노드를 가질 수 있는 트리
  • m-Way Trie, 2-3 Tree, 2-3-4 Tree 등
• Height-Balanced m-Way Tree
  
  • 특정 규칙을 통해 스스로 균형을 유지하는 m-Way Tree
  • B-Tree, B+-Tree, K-d B-Tree 등
• Spatial Tree
  • 다차원 정보를 다루기 위한 트리 구조
  • Quad Tree, Oct Tree, K-d Tree, R-Tree, R* Tree 등