08_Tree (이산수학)

1. 트리의 정의: 08_Tree (이산수학) (트리, 이진 트리, 힙 트리, BST, BBST)
   • 이진 힙 트리를 활용한 우선순위 큐
2. 트리의 구현: 07_Tree (자료구조) (표현, 연산, Traversal)
3. AVL 트리: 06_BST & AVL Trees (BST 연산, AVL 상세)

1. Tree

1.1. Definition

계층적(hierarchical) 관계를 표현하는 비선형 자료구조

• 트리 (Tree)

  • 노드와 간선으로 구성된다.
  • 하나의 부모 노드와 여러 자식 노드를 가질 수 있다.
  • 루트와 서브트리로 나눌 수 있다.
  • 사이클이 없는 그래프를 트리의 일종으로 볼 수 있다.

• Applications

  • 가계도, 컴퓨터의 폴더 구조, 탐색 트리, 힙 트리 등
  • 결정 트리 (예: 8개의 동전 문제)
  • 게임 트리

1.2. 용어

• 노드의 차수(Degree)
  • 어떤 노드의 자식 수
  • (트리의 차수는 노드들의 차수 중 최댓값)

노드 특성 관련 용어

1. 루트 노드 (Root Node)

   • 트리의 최상단에 위치한 노드
   • 부모(Predecessor)가 없다.

2. 비단말 노드(Internal Node)

   • 트리의 내부에 위치한 단말 노드가 아닌 노드
   • 자식(Successor)이 있다.

3. 단말 노드 (Leaf Node)

   • 트리의 최하단에 위치한 노드
   • 자식이 없다. (차수 0)

노드 관계 관련 용어

• 부모 노드(Parent): 어떤 노드의 바로 위 노드

• 형제 노드(Sibling): 같은 부모를 가지는 노드

• 자식 노드(Child): 어떤 노드의 바로 아래 노드들

• 조상 노드(Ancestor): 어떤 노드 위의 모든 노드

• 자손 노드(Descendant): 어떤 노드 아래의 모든 노드

위치/깊이 관련 용어

• 레벨 (Level)

  • 루트(레벨 1)부터 시작

• 깊이 (Depth)

  • 루트(깊이 0)부터 시작

• 높이 (Height)

  • 리프(높이 0)부터 시작
  • 루트에서 가장 깊은 단말 노드까지의 거리

2. Binary Tree

2.1. Definition

• Features

  • 모든 노드의 자식 수를 0~2개로 제한한 트리

  • 왼쪽 자식과 오른쪽 자식은 반드시 구별

• Applications

  • 수식 트리
  • 문법의 파싱 트리(식, 구문)
  • 호프만 코딩 트리

2.2. 종류

• 변질 이진 트리 (Degenerate Binary Tree)

  • 모든 부모 노드가 오직 하나의 자식 노드만을 가지는 이진 트리

  • 사실상 선형 연결 리스트(Linked List)와 다를 바 없으며, 이로 인해 높이/탐색 성능이 $O(n)$으로 저하된다.

  • 편향 이진 트리 (Skewed Binary Tree)

    • 변질 이진 트리 중에서도 자식 노드가 일관되게 한쪽 방향으로만 치우쳐서 뻗어나가는 트리

• 균형 이진 트리 (Balanced Binary Tree)

  • 모든 노드의 좌우 서브트리 높이 차이가 1 이하인 트리
  • $O(\lg n)$의 높이를 가진다. 대체로 자식이 2개씩 분포되어 검색에 유리한 형태이다.

• 완전 이진 트리 (Complete Binary Tree)

  • 레벨 $1$부터 $k-1$까지는 모든 노드가 2개의 자식을 가진다.
  • 마지막 레벨 $k$의 노드들은 왼쪽부터 차례로 채워져 있어야 한다.
  • 따라서 위에서 아래로, 왼쪽에서 오른쪽으로 노드를 배치한 형태

• 포화 이진 트리 (Full Binary Tree; 또는 Perfect)

  • 모든 레벨에 노드가 꽉 차있는 이진 트리

2.3. 성질

구분	Skewed	Full
노드가 n개일 때 간선 수	$n-1$	$n-1$
노드가 n개일 때 높이	$n$	$\lceil lo{g}_2(n+1)\rceil$
높이가 h일 때 노드 수	$h$	$2^h-1$

3. Binary Heap Tree

3.1. Definition

• Heap Property

  • 완전 이진 트리를 기반으로 한다.
  • 부모 노드와 자식 노드는 다음 중 하나의 힙 속성을 가진다.
    1. 최대 힙 (Max Heap)
       • 부모 노드의 값이 자식 노드의 값보다 크거나 같다. (부모 ≥ 자식)
       • 따라서 루트 노드에 최댓값이 위치한다.
    2. 최소 힙 (Min Heap)
       • 부모 노드의 값이 자식 노드의 값보다 작거나 같다. (부모 ≤ 자식)
       • 따라서 루트 노드에 최솟값이 위치한다.
  • 중복 키가 가능하다.

• Features

  • $n$개의 요소를 가진 힙의 높이는 $\Theta (\log n)$이다.
  • ==최대·최소를 $O(1)$로 반환한다.==

• 힙의 배열 표현

  • 완전 이진 트리의 성질을 이용해 배열로 표현 (인덱스 1부터 시작)
  • k의 부모: k / 2
  • k의 왼쪽 자식: k * 2
  • k의 오른쪽 자식: k * 2 + 1

• Applications

  • 우선순위 큐
  • 힙 정렬
  • 그래프 최단 경로(Dijkstra)
  • 실시간 스케줄러

4. BST

4.1. Definition

• 이진 탐색 트리 (BST; Binary Search Tree)

  • 효율적인 탐색을 위한 이진 트리 기반의 자료구조

• BST의 핵심 속성 (Key Property)

  • 유일키 (중복 키 불가능)

  • $L<V<R$ 관계 유지 (왼쪽 < 부모 < 오른쪽)

  • 어떤 노드 $x$를 기준으로,

  • 왼쪽 서브트리에 있는 모든 노드의 값은 $x$의 값보다 작거나 같다.

  • 오른쪽 서브트리에 있는 모든 노드의 값은 $x$의 값보다 크거나 같다.

• 성질

  • 서브 트리도 이진 탐색 트리이다.
  • 검색, 삽입, 삭제 등의 기본 연산 시간이 트리의 높이에 비례한다. ($O(h)$)
  • $O(\lg n)$의 높이가 기대된다.
  • 딕셔너리(Dictionary)나 우선순위 큐(Priority Queue) 구현에 사용된다.

4.2. 성능

• 연산들의 시간 복잡도: O(h) (트리의 높이 h에 비례)
  • 포화 이진 트리: h = ⌈log₂(n+1)⌉ → O(log n)
  • 완전 경사 트리: h = n → O(n)
    • 균형화가 필요 → AVL 트리

5. Balanced BST

• Applications
  • 운영체제 스케줄러(CFS: Red‑Black)
  • 데이터베이스 인덱스(B/B+‑Tree)
  • STL map/set

5.1. AVL Tree

• AVL Tree (Adelson-Velskii and Landis)

  • BST가 한쪽으로 치우치는(퇴화하는) 문제를 막기 위해,
  • 삽입/삭제 시 LL, RR, LR, RL 회전으로 스스로 균형을 유지하는 트리이다.
  • $O(\log n)$ 연산을 보장한다.

• 1번 회전

  • LL 회전: 왼쪽 자식의 왼쪽 서브트리 삽입 시
  • RR 회전: 오른쪽 자식의 오른쪽 서브트리 삽입 시

• 2번 회전

  • LR 회전: 왼쪽 자식의 오른쪽 서브트리 삽입 시
  • RL 회전: 오른쪽 자식의 왼쪽 서브트리 삽입 시

• Applications

  • Balanced BST 교육용

5.2. Red-Black Tree

• Red-Black Tree

  • 자가 균형 이진 탐색 트리(Self-Balancing BST)
  • 각 노드에 색(Red/Black)을 부여해 트리의 균형을 유지한다.

• 5가지 핵심 규칙

  1. 모든 노드는 Red 또는 Black
  2. 루트는 항상 Black
  3. 모든 리프(NIL) 노드는 Black
  4. Red 노드의 자식은 반드시 Black (Red-Red 연속 불가)
  5. 임의 노드에서 리프까지 모든 경로의 Black 노드 수는 동일 (Black-height 일치)

• 성능

  • 삽입/삭제/탐색 모두 O(log n)
  • 회전(Rotation)과 재색칠(Recoloring)으로 균형 유지

• 사용 사례

  • Java의 TreeMap, TreeSet
  • C++ STL의 map, set
  • Linux 커널 스케줄러 등

5.3. B/B+ Tree

• B-Tree

  • 모든 노드가 여러 개의 키와 자식 포인터를 가질 수 있는 균형 다중 경로 트리(Balanced Multi-way Tree)
  • 차수(order) m인 B-Tree는 각 노드가 최대 m-1개의 키와 m개의 자식을 가진다.

• 특징

  • 내부 노드에도 실제 데이터가 있어 탐색이 중간에 끝날 수 있음
  • 하지만 범위 탐색 시 트리를 전체 순회해야 해서 비효율적이다.

• B+Tree

  • B-Tree의 변형으로, 데이터베이스 인덱스에서 압도적으로 많이 쓰인다.
  • B-Tree와의 핵심 차이
    • 내부 노드는 탐색을 위한 키(인덱스)만 가지고, 실제 데이터는 오직 리프 노드에만 저장된다.
    • 리프 노드들은 연결 리스트로 이어져 있어 범위 탐색(range query)이 매우 빠르다.

• 사용 사례

  • MySQL InnoDB, PostgreSQL 등 대부분의 RDBMS 인덱스 구조