🔢계층적 자료구조, 트리(Tree)

관련글 :

힙(Heap) (문제 유형 참고)	https://waydd.tistory.com/41
이진 탐색 트리 구현 (AVL 포함)	https://waydd.tistory.com/25
그래프 개념	https://waydd.tistory.com/15
그래프 탐색 알고리즘 (DFS, BFS 참고)	https://waydd.tistory.com/11
인접 리스트, 인접 행렬 참고	https://waydd.tistory.com/94
트리에서 DFS 사용 예시	https://waydd.tistory.com/95
트리 기반 고급 자료구조	https://waydd.tistory.com/99

 

 

1. 트리(Tree) 란?

 

사이클이 없는 연결 그래프

→ 루트(root)부터 시작해 자식 노드로 내려가는 계층적 구조

→ 모든 노드는 루트에서 연결됨 (분리된 노드 없음)

• 한 노드에서 다른 노드로 가는 경로가 단 하나만 존재 (계층적 구조)
• N 개의 정점(노드) / N-1 개의 간선 으로 구성
• 사이클(순환 구조) ❌ → 비순환 그래프, 어떤 두 정점간 경로 유일
• 전체 트리는 하나의 연결 요소
• 기본적으로 간선 수 적고 구조가 제한된 희소 그래프
  → 또한 무방향 그래프 (부모-자식 관계로 볼땐 방향 있음, 특히 루트 트리나 자료구조 관점)
• 계층적 구조 표현에 적합  ex) 파일시스템, 조직도

※ 트리 예시
         0                ← 깊이 0(루트), 높이 2
      /      \
    1        2           ← 깊이 1
           /      \
        3          4     ← 깊이 2 (리프 노드), 높이 0
- 0은 루트(root) 노드 (가장 위의 시작점)
- 간선 목록: (0-1), (0-2), (2-3), (2-4)
- 1의 높이는 0(리프라서), 2의 높이는 1
- 1, 2는 0의 자식(child)
- 서브트리 : 2를 루트로 하는 [2, 3, 4]

※ 트리에 방향이 있다고 설명하는 경우
- 이론 상 트리 구조는 기본적으로 방향을 명시하지 않음
- 이진 트리, 서브트리, 트리 DP 같은 구현 시 부모→자식 구조를 명확히 하기 위해 방향 부여함
- 즉, 루트가 정해지면 방향을 부여하여 사용 (암묵적)
- 트리 순회, 루트가 있는 트리 를 사용하는 보통의 문제 상황에선, 루트가 있는 방향 트리 (rooted tree) 로서 사용

 

- 트리의 구성 요소

• 루트(root) : 트리의 시작점, 부모가 없는 유일한 노드 (보통 0, 1)
• 노드(node) : 트리를 구성하는 각 원소로, 정점(vertex) 이라고도 함
• 간선(edge) : 두 노드를 연결하는 선 또는 연결고리, 가중치(weight)를 가질 수도 있고 없을 수도 있음
  → 간선이 없으면 해당 노드 간 직접적인 경로가 존재하지 않음을 의미
• 경로(Path) : 간선을 따라 연결된 노드들의 순서
• 거리 : 경로 상의 간선의 개수 또는 간선의 가중치의 합
• 깊이(depth) : 루트에서 해당 노드까지의 거리(단계/ 간선 수), 루트의 깊이는 0
  → 어떤 노드가 루트로부터 얼마나 멀리 떨어져 있는지 를 숫자로 표현 한 것 (= 개별 노드의 위치 관점)
  → 루트를 기준으로 항상 0부터 시작
• 레벨(level) : 깊이와 유사, 루트부터 층별(계층 번호)로 나눈 트리 구조 상의 위치 (= 트리의 전체 계층, 같은 층 단위 관점)
  → 보통 1부터 또는 0부터 시작 (문맥에 따라 다름)
      예시) 정의를 1부터 시작한다면, 루트-0 (레벨 1, 높이는 0), 노드-1, 2(레벨2, 높이 1), ...
• 높이(height) : 해당 노드로부터 가장 깊은 리프까지의 거리(간선 수), 트리의 전체 높이 = 루트 기준
  → 리프 노드의 높이 = 0, 부모는 자식 중 최대 높이 + 1
• 트리의 지름(diameter) : 트리 내에서 가장 먼 두 정점 사이의 거리 (임의의 두 노드 X, Y 간 거리 중 가장 긴 거리)
• 부모-자식 노드 : 각각 다른 노드를 바로 위에서 가리키는 노드(= 루트 방향으로 가까운 쪽)와 부모로부터 연결된 하위 노드
  →  모든 노드는 단 하나의 부모만 가짐 (루트 제외)
• 형제 : 같은 부모를 가진 노드들, 같은 depth를 가짐
• 리프 노드(말단 노드) : 자식이 없는 노드, 끝 노드, 간선을 1개뿐
• 조상 (Ancestor) : 어떤 노드에서 루트 방향으로 올라가는 노드
• 서브 트리 : 트리 내부에서 어떤 노드를 루트로 하는 트리 전체 (부분 트리, 하위 트리) → DP, 재귀적 탐색 활용가능

 

- 활용 사례

이진탐색트리(BST)	오름차순 자동정렬(= 중위 순회 결과)되는 트리기반 set, map 구현 / 데이터베이스 인덱싱
힙(Heap)	우선순위 큐, 스케줄러, Dijkstra 알고리즘
파싱 트리 (문법 분석기)	컴파일러의 파서, 수식 계산기
디렉터리 구조	Windows, Linux 디렉터리 구조 ( 폴더/파일의 계층적 구조를 표현 )
네트워크 라우팅	인터넷 패킷 라우팅, spanning tree
게임 트리	체스 AI, 틱택토, 미니맥스 알고리즘

 

 

2. 이진 트리와 이진 탐색 트리

 

- 이진 트리 (Binary Tree) 

• 모든 노드가 최대 두개의 자식 노드를 가질 수 있는 가장 기본적인 트리 구조 (값의 크기나 배치에 대한 규칙은 없음)
• 왼쪽 자식 : 왼쪽 서브트리에 있는 자식 노드
  오른쪽 자식 : 오른쪽 서브트리에 있는 자식 노드
• 포화 이진 트리 (Full / Perfect) : 모든 노드가 0개 또는 2개의 자식을 가짐 (= 모든 레벨에 노드가 가득 참)
  → 피라미드 형태로 모든 리프 노드의 깊이가 같음
  → 노드 수는 2^h - 1개 (h는 높이)
  완전 이진 트리 (Complete) : 마지막 레벨만 왼쪽부터 채워진 트리 (나머지 모든 레벨은 포화)
• 힙, 이진탐색트리(BST)는 이진 트리의 한종류 (즉 특수한 트리 자료구조, 각기 다른 규칙을 따름)

※ 형태 예시
         A
      /      \
    B        C
   /             \
 D               E 

※ 포화 이진 트리 예시
         A
      /      \
    B        C
  /    \     /    \
D     E  F    G 

※ 완전 이진 트리 예시
         A
      /      \
    B        C
  /    \     / 
D     E  F     ← 마지막 레벨이 왼쪽부터 차례대로 채워짐

 

- 이진 탐색 트리(Binary Search Tree, BST)

• 이진 트리 기반, 탐색을 빠르게 하기 위한 규칙을 따름
• BST의 규칙 : 왼쪽 자식 < 부모 < 오른쪽 자식
  → 모든 서브트리도 BST 구조를 만족해야 함
  → 삽입 규칙 없이 넣으면 한쪽으로 치우친 일반 연결 리스트처럼 변함
• 전위, 중위, 후위 순회 모두 사용 가능
  → 중위 순회는 항상 오름차순 정렬된 결과 보장,  ex) 정렬된 리스트 만들기, K번째 작은 수 찾기
  → 전위는 트리 복사/직렬화, 후위는 트리 삭제시 유용
• 정렬된 자료 검색, 삽입, 삭제에 유리
• 재귀, 포인터 기반으로 구현
• 탐색/삽입/삭제 속도 : 평균 O(log N), 최악 O(N) 
  → 탐색(search) : 루트부터 비교하며 하위 노드로 내려감 
  → 삽입(insert) : 적절한 위치를 찾아 삽입
  → 삭제(delete) : 삭제 후 재구성(자식, 후계자 교체 등)

※ 형태 예시
        10
      /      \
    5       15
  /    \         \
2      7       20

※ 왜 평균 O(log N), 최악은 O(N)일까? (균형이 중요한 이유)
- BST는 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼
- 그래서 값을 찾을 때 한쪽 방향으로만 내려가면서 탐색함 (루트 → 리프까지)
- 삽입 순서에 따라 한쪽으로 치우치면( = 트리의 높이가 크면 ), 트리가 선형 구조(연결 리스트처럼) → O(N)
  (트리의 높이 = 최악의 경우 내려가는 단계 수)
- 트리가 균형 잡혀 있을 경우 (양쪽 자식이 비슷한 수만큼 있음), 높이는 log₂N 수준 → O(log N) 
  (각 층의 노드 수는 등비수열, 로그는 거듭제곱(지수)의 역연산)
- 때문에 항상 정렬 상태 유지 + 트리의 높이가 작아야 효율적
  → AVL 트리, 레드-블랙 트리 같은 균형 이진탐색트리 사용

 

- 최대 힙 (Max Heap)

• 완전 이진 트리 기반(왼쪽부터 차례대로 채움) 의 자료구조, 루트 노드가 항상 최댓값을 유지하는 특징을 가짐
• 힙 규칙 : 부모 ≥ 자식 (Max Heap) → 항상 가장 큰 값이 루트 / 부모 ≤ 자식 (Min Heap)
• 우선순위 큐, 힙 정렬 에서 사용
• 보통 배열로 구현 (인덱스 기반)
• 탐색 속도 : O(N) (값 위치 무관)

※ 형태 예시
        20
      /      \
   15      10
  /    \    /
2     7  2

 

 

3. 트리 순회 방식

 

DFS 또는 BFS 기반으로 실행되는 순서를 정의하는 방식

 

- 포지션 기반 순회 (DFS 기반)

• 이진 트리에 특화된 개념으로 루트, 왼쪽, 오른쪽 순서를 기준으로 정한 순회 방식
  → 루트로부터 왼쪽 자식 → 왼쪽 자식 → ... 이런식으로 한쪽 끝까지 파고들기 때문에 깊이 우선
• 각기 결과값에 대한 부분은 ※ BST 예시를 참고

※ BST 예시
         8
      /      \
    4      10
  /    \         \ 
2     6        20

 

① 전위 순회 (Pre-order) : 루트 → 왼쪽 → 오른쪽 (부모 먼저)

8 → 4 → 2 → 6 → 10 → 20

 

② 중위 순회 (In-order) : 왼쪽 → 루트 → 오른쪽 (정렬 순서, BST에서 중요)

2 → 4 → 6 → 8 → 10 → 20

 

③ 후위 순회 (Post-order) : 왼쪽 → 오른쪽 → 루트 (자식 먼저, 부모 마지막)

2 → 6 → 4 → 20 → 10 → 8

 

 

- 레벨 순회 (Level-order)  ( BFS 기반)

• 트리의 각 레벨(깊이)을 왼쪽 → 오른쪽 순서로 차례차례 탐색하는 방식
  → 같은 레벨의 노드들부터 탐색하기 때문에 너비 우선
• 루트 → 1층 자식들 → 2층 자식들 → ... (레벨 순서대로 왼→오)

 

 

4. 탐색 알고리즘 (DFS/BFS)

 

일반 트리(N-ary 트리 포함) 에서 자식 수와 위치에 관계없는 범용 순회

→ 그래프 전반에 적용되는 탐색 알고리즘

※ N-ary 트리 : 다진 트리의 특수형, 자식이 최대 N개 인 트리
※ 다진 트리 (다방향 트리) : 자식이 2개 이상일 수 있는 트리 (자식 개수 제한 없음),  ex) 디렉토리 구조

※ 시간 복잡도 O(V)인 이유
- O(V + E) = O(V + (V - 1)) = O(2V - 1) = O(V) (단순화)
- 시간 복잡도는 입력 크기가 매우 커질때 성능의 증가를 확인하는 것이므로,
  작은 차이(상수, 낮은 차수 항)는 생략하여 성능 경향성만 남김

 

- 깊이 우선 (DFS)

• 노드 위치 (왼쪽/오른쪽)
• 재귀/스택 기반
  → 트리는 자식 노드를 통해 재귀적으로 내려가야 함
  → 본질적으로 DFS 구조 + 재귀함수 구현 간단, 트리 문제에 주로 사용
• 중위 순회는 BST에서 정렬된 결과
• 인접 리스트 유리 (O(V) 수준)
• 시간 복잡도: O(N)

트리 탐색	부모 찾기, 노드 깊이 구하기
트리 DP	BOJ 1949 (우수 마을), BOJ 2213 (트리에서 독립집합)
트리 지름	BOJ 1967, BOJ 1167
루트에서 리프까지 거리 계산	DFS가 더 빈번하게 쓰임

 

- 너비 우선 (BFS)

• 노드 깊이 (레벨)
• 큐(Queue) 기반, 큐를 사용해 순서대로 노드를 꺼냄
• 정렬은 아님
• 마찬가지로 인접 리스트를 더 자주 사용, 특정 상황일 때는 인접 행렬 사용
• 시간 복잡도: O(N)