[자료구조/알고리즘] 균형 이진 탐색 트리(Balanced Binary Search Tree)

균형 이진 탐색 트리(Balanced Binary Search Tree)

• 정의
  - 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
• 종류
  - AVL 트리
  - Red-Black 트리

이진 탐색 트리의 편향

• 이진 탐색 트리의 경우 데이터 삽입 순서에 따라 편향이 발생할 수 있음
  

AVL 트리

• 정의
  - 노드가 삽입, 삭제될 때 트리의 균형을 체그하고 유지하는 트리
• 특징
  - 시간복잡도 O(logN)
  - 각 노드의 BF를 [-1,0, 1]만 가지게 하여 균형을 유지
  • BF(Balance Factor): 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

리벨런싱

• 균형이 깨진 경우
  - BF가 양수이면 왼쪽 서브트리에 불균형이 발생
  - BF가 음수이면 오른쪽 서브트리에 불균형이 발생
• 회전 연산을 통해 균형을 유지
  - 단순 회전: LL, RR
  - 이중 회전: LR, RL

LL

• 1회 회전
• 삽입, 삭제 노드의 BF가 양수이고 그 노드의 왼쪽 노드 BF가 양수일 때 연산
  

RR

• 1회 회전
• 삽입, 삭제 노드의 BF가 음수이고 그 노드의 왼쪽 노드 BF가 음수일 때 연산
  

LR

• 2회 회전
• 삽입, 삭제 노드의 BF가 양수이고 그 노드의 왼쪽 노드 BF가 음수일 때 연산
  

RL

• 2회 회전
• 삽입, 삭제 노드의 BF가 음수이고 그 노드의 왼쪽 노드 BF가 양수일 때 연산
  

Red-Black 트리

• 조건
  - root노드와 leaf 노드의 색은 black
  - red 색 노드의 자식은 black(double red 불가)
  - 모든 leaf 노드에서 root 노드까지 가는 경로의 black 노드 수는 같음
  

Red-Black 트리 vs AVL 트리

• Tree 체계가 잡힌 후 탐색이 많은 경우 AVL트리가 유리
• 삽입, 삭제가 빈번한 경우 Red-Black 트리가 유리

구현(TODO)