3주차 - 트리가 한쪽으로 쏠리는 것을 막는 균형 이진 트리, RB트리

트리가 한쪽으로 쏠리는 것을 막는 균형 이진 트리

이진 탐색 트리인 BST의 한 종류. 트리가 한쪽으로 쏠리는 거를 막아서 탐색 / 삽입 / 삭제를 거의 항상 O(log n)으로 유지하는 균형 이진 트리.

RB트리 간단하게

• BST
• • 트리가 한쪽으로 너무 길어지지 않도록 Red / Black 규칙을 추가
• • 규칙이 깨지면 Rotation + Recoloring으로 복구

BST는 데이터가 한쪽에 몰리면 탐색이 O(n)

BST에서는 항상 왼쪽 < 부모 < 오른쪽을 유지. 하지만 데이터 자체가 한쪽에 몰릴 수도 있음.

균형 잡힌 BST

        10
       /  \
      5    20
     / \   / \
    3   7 15 30

한쪽으로 쏠린 BST

1
 \
  2
   \
    3
     \
      4
       \
        5

이러면 탐색이 O(n)

RB트리는 색 규칙을 추가하여 기울어지지 않도록 유지

RB트리는 여기에 색 규칙을 추가하여 기울어지지 않도록 유지.

핵심 규칙

각 노드는 Red or Black

            10(B)
           /     \
        5(R)     20(R)
       /   \     /   \
    3(B) 7(B) 15(B) 30(B)

1. 모든 노드는 Red or Black
2. 루트는 Black
3. 모든 NIL(Null) 리프는 Black
4. Red 노드 자식은 반드시 블랙
5. 어떤 노드에서 아래쪽 NIL(Null) 리프까지 가는 모든 경로에는 같은 개수의 Black 노드가 있음

Black Height가 한쪽이 지나치게 길어지는 것을 막음

• 어떠한 노드에서 NIL까지 내려갈 때 지나가는 Black 노드 개수를 Black Height라고 함
• RB 트리는 모든 경로의 Black Height가 같아야 함
• 한쪽이 지나치게 길어지는 것을 막음

삽입: 새 노드는 일단 Red

새로 삽입되는 노드는 일단 Red. (Black으로 넣을 경우 Black Height가 바로 바뀔 수도 있음)

들어가기 전

Rotation이란,

BST의 특성을 유지한 채 특정 노드를 축으로 삼아 트리의 구조를 재조정하여 균형을 맞추는 연산

• BST 규칙 유지: 회전 전후에도 왼쪽 자식 ≤ 부모 ≤ 오른쪽 자식 대소 관계 유지
• 균형 재조정: 트리의 높이가 너무 커지지 않도록 구조를 바꿔서 탐색 효율 O(logn) 보장

회전 2가지

• 좌회전 (Left Rotation)
  • Node x를 기준으로 오른쪽 자식 y를 끌어올리는 구조
  • x는 y의 왼쪽 자식이 되고 y가 기존 x의 자리를 대체하여 서브 트리의 새로운 루트가 됨
• 우회전 (Right Rotation)
  • Node y를 기준으로 왼쪽 자식 x를 끌어올리는 구조
  • y는 x의 왼쪽 자식이 되고 x가 기존 y의 자리를 대체하여 서브 트리의 새로운 루트가 됨

Recoloring이란

새로 노드 삽입 시 발생하는 Double Red 위반을 해결하기 위하여 트리의 구조를 바꾸지 않고 노드의 색상만 변경하는 작업

• 새로 삽입한 노드의 부모 노드와 삼촌 노드의 색상이 모두 빨간색일 때 발생

동작 방식

1. 부모 노드와 삼촌 노드의 색상을 검은색(Black)으로 바꿈
2. 조상(할아버지) 노드의 색상을 빨간색(Red)으로 바꿈
3. 단, 조상 노드가 루트(Root) 노드라면 최종적으로 다시 검은색(Black)으로 고정

10, 20, 30을 순서대로 삽입하면

10
20
30
# 을 순서대로 삽입

10을 넣으면 루트라 Black

20(R) -> 30(R)

이런 식으로 Red Red가 발생. 이것을 Rotation과 Recoloring으로 처리

       20
      /  \
    10    30

이렇게 회전시키면 높이만 줄었음, BST 순서는 유지됨. 이후 색을 재 조정하면

       20(B)
      /  \
    10(R) 30(R)

규칙이 다시 만족

G, P, U, N

        Grandparent
        /         \
     Parent       Uncle
       |
      New

여기서 G = Grandparent P = Parent U = Uncle N = New Node