Data Structure_트리
트리는 계층적인 구조를 나타내는 자료 구조로, 노드(Node)들의 집합으로 구성됩니다. 각 노드는 부모(Parent)와 자식(Children) 노드로 연결되며, 최상위 노드는 루트(Root) 노드라고 합니다. 자식 노드가 없는 노드는 단말(Leaf) 노드라고 합니다. 트리는 그래프의 한 종류로, 다양한 종류와 활용 목적이 있습니다.
트리의 종류
- 이진 트리(Binary Tree)
- 이진 탐색 트리(Binary Search Tree, BST)
- AVL 트리
- 힙(Heap) 트리
- m-원 트리(m-ary Tree)
- 레드-블랙(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 트리와 유사한 균형 이진 탐색 트리로, 특정 규칙을 유지하며 균형을 맞춥니다.
- 규칙:
- 모든 노드는 레드(Red) 또는 블랙(Black) 중 하나
- 루트 노드는 항상 블랙
- 모든 단말 노드는 블랙
- 레드 노드는 연속될 수 없음 (레드-레드 연속 금지)
- 루트에서 단말까지 모든 경로의 블랙 노드 수는 동일
- 균형을 유지하기 위해 회전(Rotation)과 색 변경을 수행
레드-블랙 트리는 AVL 트리보다 삽입과 삭제 연산이 빠르며, 데이터베이스 및 운영체제의 스케줄링 시스템에서 활용됩니다.