트리는 계층적인 구조를 나타내는 자료 구조로, 노드(Node)들의 집합으로 구성됩니다. 각 노드는 부모(Parent)와 자식(Children) 노드로 연결되며, 최상위 노드는 루트(Root) 노드라고 합니다. 자식 노드가 없는 노드는 단말(Leaf) 노드라고 합니다. 트리는 그래프의 한 종류로, 다양한 종류와 활용 목적이 있습니다.



트리의 종류

  1. 이진 트리(Binary Tree)
  2. 이진 탐색 트리(Binary Search Tree, BST)
  3. AVL 트리
  4. 힙(Heap) 트리
  5. m-원 트리(m-ary Tree)
  6. 레드-블랙(R-B) 트리


이진 트리 (Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.

  • 마지막 레벨을 제외하고 모든 노드가 채워져 있으면 완전 이진 트리(Complete Binary Tree)
  • 마지막 레벨까지 노드들이 꽉 차 있으면 포화 이진 트리(Full Binary Tree)


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

이진 트리의 한 종류로, 각 노드가 특정한 순서로 정렬되어 있습니다.

  • 왼쪽 서브트리의 모든 노드는 현재 노드보다 작음
  • 오른쪽 서브트리의 모든 노드는 현재 노드보다 큼
  • 검색 시 평균 O(log N), 편향되면 O(N)


AVL 트리

이진 탐색 트리의 단점을 보완한 균형 트리입니다.

  • 노드 간 높이 균형을 유지하여 검색, 삽입, 삭제 속도를 일정하게 유지
  • 균형 인수(Balance Factor, BF): 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이
  • 균형을 유지하기 위해 LL, RR, LR, RL 회전을 수행


힙 (Heap) 트리

완전 이진 트리의 일종으로, 각 노드의 값이 부모-자식 관계에서 정렬된 상태를 유지합니다.

  • 최소 힙(Min Heap): 부모 노드가 자식보다 항상 작음
  • 최대 힙(Max Heap): 부모 노드가 자식보다 항상 큼
  • 주요 활용: 우선순위 큐, 다익스트라 알고리즘, 힙 정렬


m-원 트리 (m-ary Tree)

각 노드가 최대 m개의 자식을 가질 수 있는 트리입니다.

  • m이 2이면 이진 트리
  • n레벨에서는 최대 m^(n-1) 개의 노드 보유 가능
  • 데이터가 많아질수록 높이가 길어지는 이진 트리의 문제를 보완하기 위해 설계됨

B-트리(m-원 트리의 확장)

  • 균형을 유지하며 대용량 데이터를 효과적으로 저장 및 검색
  • 데이터베이스 시스템 및 파일 시스템에서 활용됨
  • 특징:
    • 루트 노드는 최소 2개의 키를 가짐
    • underflow 방지: 키의 개수가 m/2 - 1보다 작아지지 않도록 유지
    • overflow 처리: 키가 가득 찬 경우 중앙 키를 부모 노드로 이동 후 분할


레드-블랙(R-B) 트리

AVL 트리와 유사한 균형 이진 탐색 트리로, 특정 규칙을 유지하며 균형을 맞춥니다.

  • 규칙:
    1. 모든 노드는 레드(Red) 또는 블랙(Black) 중 하나
    2. 루트 노드는 항상 블랙
    3. 모든 단말 노드는 블랙
    4. 레드 노드는 연속될 수 없음 (레드-레드 연속 금지)
    5. 루트에서 단말까지 모든 경로의 블랙 노드 수는 동일
  • 균형을 유지하기 위해 회전(Rotation)과 색 변경을 수행

레드-블랙 트리는 AVL 트리보다 삽입과 삭제 연산이 빠르며, 데이터베이스 및 운영체제의 스케줄링 시스템에서 활용됩니다.