트리

Tree 트리(Tree)는 계층적 구조를 가지는 비선형 자료 구조로, 하나의 루트 노드(Root Node)에서 시작하여 여러 개의 자식 노드를 가질 수 있다. 트리는 그래프의 한 종류이며, 방향성이 있는 비순환 그래프(DAG, Directed Acyclic Graph)로 볼 수 있다.

• 비선형, 비순환 구조

1 트리의 특성

• 트리는 노드와 간선으로 구성된다.
• 순환(Cycle)이 존재하지 않는다.
• n개의 노드를 가진 트리는 항상 (n-1)개의 간선을 가진다.
• 루트에서 특정 노드까지의 경로는 유일하다.

관련 용어

용어	의미
차수(degree)	노드의 부족 트리의 개수 트리 전체의 차수: 트리에 속한 최대 차수
단말 노드(leaf, terminal)	차수가 0인, 가장 끝의 노드
내부 노드(internal)	차수가 1 이상인, 단말이 아닌 노드
부모(parent)	바로 상위 노드
자식(child)	바로 하위 노드
형제(sibling)	부모가 같은 노드
조상(ancestor)	상위 노드, 부모 노드들의 집합
자손(descendant)	하위 노드, 자식 노드들의 집합
레벨(level)	상위 노드를 기준으로 한 깊이
깊이(depth)	트리에 속한 최대 레벨

예시

        A        → 루트 노드 (깊이 0)
       / \
      B   C      → 깊이 1
     / \   \
    D   E   F    → 깊이 2 (리프 노드: D, E, F)

이 트리에서:

• 루트 노드 - A
• 깊이 - D, E, F의 깊이는 2
• 차수 - A의 차수는 2, B의 차수는 2, C의 차수는 1
• 높이 - 2 (루트 A에서 가장 깊은 리프까지의 거리

주의 사항은 "거리"는 간선의 수를 기준으로 한다는 것이다. 노드를 기준으로 3개 층이 있는 트리의 높이, 깊이는 모두 3이 아니라 2다.

트리의 공식

높이와 노드 개수 관계

이진 트리에서 높이 h와 최대 노드 수 N의 관계:

• 최대 노드 개수:
  • N = 2^(h+1) - 1
• 최소 노드 개수(편향 트리의 경우):
  • N = h + 1

리프 노드 개수 공식

• 이진 트리에서 리프 노드 개수 L과 내부 노드 개수 N의 관계
  • L = N + 1

균형 이진 트리에서 높이와 노드 개수 관계

균형 잡힌 이진 트리(Balanced Binary Tree)에서:

• 높이 h일 때 최소 노드 개수
  • N = 2^h - 1
• 높이 h일 때 최대 노드 개수
  • N = 2^(h+1) - 1

트리의 종류

• 일반 트리(General Tree): 노드가 제한 없이 여러 자식을 가질 수 있는 트리.
• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가질 수 있는 트리.
• 이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식은 부모보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 가지는 트리.
• 균형 이진 트리(Balanced Binary Tree): 높이를 균등하게 유지하는 트리 (예: AVL 트리, 레드-블랙 트리).
• 힙(Heap): 부모 노드가 자식 노드보다 크거나 작은 값을 가지는 트리.
• B-트리(B-Tree): 데이터베이스 및 파일 시스템에서 사용되는 균형 트리.

트리의 활용

• 검색 및 정렬:
  • 검색: log(n)의 효율
  • 정렬: Heap 구조 이용
• 파일 시스템: 디렉터리 구조 표현.
• 데이터베이스: B-트리 기반 인덱싱.
  • 인덱스: B 트리, AVL 트리, T 트리 등
• 인공지능: 의사 결정 트리(Decision Tree).
• 그래픽스: 씬 그래프(Scene Graph) 구조.

트리의 순회

Tree Traversal

트리를 조회하는 방식

전위 순회(Preorder)

• 깊이 우선 순회(DFT, Depth-First Traversal) 라고도 하며, 주로 트리를 복사하거나 전위표기법을 구하는데 사용한다.
• 복사할 때 사용하는 이유는 트리의 노드부터 복사해야하기 때문이다.
• 다음과 같은 방법으로 진행한다.
  1. 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.

중위 순회(Inorder)

• 대칭 순회(symmetric) 라고도 하며, 이진 탐색 트리(BST, Binary Search Tree) 에서 값을 가져올 때 주로 사용한다.
• 다음과 같은 방법으로 진행한다.
  1. 왼쪽 서브 트리를 중위 순회한다.
  2. 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.

후위 순회(Postorder)

• 값을 삭제할 때 주로 사용한다. 그 이유는 루트 노드를 지우기 전에 하위 노드를 먼저 지워야하기 때문이다.
• 다음과 같은 방법으로 진행한다.
  1. 왼쪽 서브 트리를 후위 순회한다.
  2. 오른쪽 서브 트리를 후위 순회한다.
  3. 노드를 방문한다.

레벨 순서 순회(level-order)

• 너비 우선 순회(breadth-first traversal) 라고도 한다.
• 모든 노드를 낮은 레벨부터 차례대로 순회한다.

이진 트리

Binary Tree