이전 이야기

• 이진 검색 트리는 검색과 삽입, 삭제에 평균 Θ(logn) 시간이 소요되지만 운이 나쁘면 트리 모양이 균형을 이루지 못합니다.
• 균형이 많이 깨지면 다음과 같은 트리가 나타납니다.
  
  • 이와 같은 경우는 검색과 삽입, 삭제에 평균 Θ(n) 시간이 소요됩니다.

균형 검색 트리

• 균형 검색 트리는 최악의 경우에도 이진 트리의 균형이 맞도록 유지해서 작업들이 항상 O(logn) 시간을 보장합니다.
• 이진 검색 트리에서는 분기할 때 최대 2개로 제한되는데 이보다 더 많이 분기할 수 있는 트리들도 있다. 🠔 다진 검색 트리
  • 다진 검색 트리에서는 균형이 더 중요하다.

---

AVL 트리

• AVL 트리
  • Adelson-Velskii와 Landis 두 사람이 고안한 트리
  • 이진 검색 트리가 항상 균형을 유지하도록 운영하는 예시
  • AVL 트리는 트리 내의 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리이다.

---

균형이 깨진 AVL 트리의 수선

• AVL 트리의 균형이 깨지면 즉시 수선 과정에 들어간다.
• 수선 시, 다음과 같은 회전 알고리즘을 통해 수선한다.

좌회전(t): 🠔 t: 회전의 중심 노드
	RChild 🠔 t.right
    RLChild 🠔 RChild.left
    RChild.left 🠔 t
    t.right 🠔 RLChild
    t.height 🠔 max(t.right.height, t.left.height) + 1
    RChild.height 🠔 max(RChild.right.height, RChild.left.height) + 1

우회전(t): 🠔 t: 회전의 중심 노드
	LChild 🠔 t.left
    LRChild 🠔 LChild.left
    LChild.left 🠔 t
    t.left 🠔 LRChild
    t.height 🠔 max(t.left.height, t.right.height) + 1
    LChild.height 🠔 max(LChild.right.height, LChild.left.height) + 1

EX) 좌회전으로 두 곳의 불균형을 해결하는 예

• 하지만, 다음과 같이 한 번의 회전으로 불균형을 해소되지 않을 수가 있다.

• 이러한 상황을 해결하기 위해 t를 루트로 하는 트리 수선 작업은 t의 네 손자 서브 트리 중 가장 깊은 것에 따라 네 가지 유형으로 나뉜다.
  • LL
    • t.left.left가 가장 깊음
  • 
  • LR
    • t.left.right가 가장 깊음
  • 
  • RR
    • t.right.right가 가장 깊음
  • 
  • RL
    • t.right.left가 가장 깊음
  • 

balanceAVL(t, type):
  switch type:
    case LL: 우회전(t)
    case LR: 좌회전(t.left)
    		balanceAVL(t, LL)
    case RR: 좌회전(t)
    case RL: 우회전(t.right)
    		balanceAVL(t, RR)

구현 / Code

Github

---

레드-블랙 트리

• AVL 트리와 함께 균형을 맞추면서 운영하는 대표적인 균형 이진 검색 트리
• RB 트리
• 노드에 두 가지 색을 칠해서 균형을 맞춘다.
• RB트리는 우선 null 리프 노드를 가정한다.

RB 특성

• 루트는 블랙
• 모든 리프 노드는 블랙
• 루트로부터 임의의 리프 노드에 이르는 경로에 레드 노드 2개가 연속으로 출현하지 못한다.
• 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

RB 수선

• RB 트리에서 노드를 삽입할 때는
  먼저 이진 검색 트리의 삽입 알고리즘에 따라 삽입한 다음 새 노드의 색상은 일단 레드로 칠한다.
  이 노드를 x라고 하자.

1. 부모 노드 p가 블랙일 경우

• RB 특성을 깨지 않는다.

2. 부모 노드 p가 레드일 경우

• Case 1: s가 레드
• Case 2: s가 블랙
  • Case 2-1: s가 p의 오른자식
  • Case 2-2: s가 p의 왼자식

---

성능 평가

n개의 Key로 구성된 레드 블랙 트리가 가질 수 있는 최대 Depth(Level)는 O(logn)이다.

pf) 레드나 블랙 색상을 고려하지 않고, 가장 이상적으로 꽉 채워진 트리의 Depth는 ⌊logn⌋+1이다.
그러므로, 레드 블랙 트리가 아무리 잘 만들어져도
루트에서 임의의 Leaf까지 이르는 경로에 존재하는 블랙 노드의 개수는 ⌊logn⌋+1을 넘을 수 없다.

레드 블랙 특성 3에 따라, 레드 노드는 두 개가 연속해서 존재할 수 없다.
그러므로 루트에서 임의의 Leaf에 이르느 경로에서 레드 노드는 블랙 노드의 개수보다 많을 수 없다.
즉, 루트에서 임의의 Leaf에 이르는 경로의 길이는 2(⌊logn⌋+1)을 넘을 수 없다.
이는 점근적으로 O(logn)에 비례한다.

레드 블랙 트리에서의 검색 연산 = O(logn)

레드 블랙 트리에서의 삽입 연산 = O(logn)

• Case 1은 다시 Case 1을 재귀적으로 호출할 가능성이 있으므로, (루트까지 올라갈 수 있다.)
  최악의 경우 O(logn)에 비례하는 시간내에 해결된다.
• Case 2의 경우, 상수 시간내에 해결된다.

레드 블랙 트리에서의 삭제 연산 = O(logn)

• Case 1-(1), Case -(2), Case -(3)의 경우, 상수 시간내에 해결된다.
• Case 2-(4)는 Case 1-(1), Case 1-(2), Case 1-(3) 중 하나로 이동하므로, 이 또한 상수 시간내에 해결된다.
• Case 2-(1)은 무보 노드에서 같은 상황이 다시 반복되어 재귀적으로 처리해야 할 가능성이 있으므로, (루트까지 올라갈 수 있다.)
  최악의 경우 O(logn)에 비례하는 시간내에 해결된다.

---

출처

wiki