[자료구조] 트리(Tree) 시리즈 1: 트리(Tree)란?

트리란?

• 트리는 계층적 관계를 표현하는 비선형 자료구조다. 노드(node)들과 그 노드들을 연결하는 간선(edge)들로 구성되어 트리 모양의 형태를 가진다.

---

트리의 구조

• 루트(Root): 트리의 최상위에 있는 노드
• 노드(Node): 트리를 구성하는 각 요소
• 간선(Edge): 노드와 노드를 연결하는 선
• 부모 노드(Parent Node): 서브트리를 가지는 노드
• 자식 노드(Child Node): 부모 노드 밑에 연결된 노드
• 형제 노드(Sibling Node): 부모가 같은 자식 노드들
• 리프 노드(Leaf Node): 자식이 없는 노드
• 내부 노드(Internal Node): 적어도 하나의 자식을 가진 노드
• 서브트리(Sub Tree): 큰트리의 속하는 작은 트리

---

트리의 특징

• 계층적 구조
  • 트리는 계층적 구조를 가진다. 하나의 루트 노드에서 시작하여 아래로 계층적으로 확장되며, 각 노드는 단 하나의 부모 노드를 가진다. (루트 노드 제외).
• 연결성과 방향성
  • 모든 노드는 부모-자식 관계로 연결되어 있으며, 부모에서 자식으로의 단방향 연결을 가집니다.
  • n개의 노드를 가진 트리는 항상 n-1개의 간선(edge)을 가진다.
  • 노드 간에 순환 구조가 존재하지 않으며, 임의의 두 노드 사이에는 오직 하나의 유일한 경로만 존재한다.

• 재귀적 구조
  • 각 노드는 그 자체로 하위 트리의 루트가 될 수 있으며, 0개 이상의 자식 노드를 가질 수 있습니다.
• 비선형성
  • 트리는 데이터를 순차적으로 저장하지 않는 비선형 자료구조로, 계층적 관계를 표현하는 데 매우 적합하다.
• 그래프의 특수 형태
  • 트리는 특수한 형태의 그래프다. 순환이 없는 연결된 그래프이며, 이로 인해 많은 그래프 알고리즘을 트리에 적용할 수 있다.

---

트리의 종류

• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가질 수 있는 트리
• 이진 탐색 트리(Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리
• 균형 트리(Balanced Tree): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리 (예: AVL 트리, 레드-블랙 트리)
• B-트리: 데이터베이스와 파일 시스템에서 널리 사용되는 자체 균형 트리

---

트리의 실제 응용 사례

• 파일 시스템 구조
• DOM 오브젝트
• 데이터베이스 인덱싱

---

참고

[자료구조] 트리 (Tree)

 

[자료구조] 트리(Tree)란 - Heee's Development Blog

---