RBT(뀼)

박지성 ·2025년 4월 19일

시작하기 전에

우선 나무위키를 읽어보자
레드 블랙 트리

나무위키로 공부를 시작하면 흥미를 유발하기 좋다
또한 공부하는 느낌이 안들어서 재미가 있다.
아님말고

BST를 먼저 알아보자

이진 탐색 트리(Binary Search Tree)
근본 트리 자료구조이다.

규칙
1. 왼쪽은 나보다 작다.
2. 오른쪽은 나보다 크다.

       8
     /   \
    3     10
   / \      \
  1   6     14
     / \    /
    4   7  13

다만 이 친구는 결함이 있다.

아차차!

이런 경우에는 그냥 링크드리스트 그 잡채가 되어버린다.

이러면 탐색을 위한 BST의 존재 의미가 없어진다.

AVL의 탄생

1962년에 어떤 개발자가 BST가 너무 안 좋아서 AVL을 만들었다

AVL은 BST의 균형이 안맞는 문제를 해결을 할 수 있다

삽입과 삭제를 진행할 때 높이를 체크해서 균형을 바로 잡는다

그러나

AVL은 너무 FM이라 단 하나의 높이가 안 맞아도 수정을 해버리는 아주 귀찮은 친구이다

RBT의 탄생

개발자 입장에서는 AVL은 너무 귀찮다
좋은 자료구조는 맞지만 삭제는 너무 귀찮고 회전도 너무 많이한다

그래서 적당히 대충하는 트리가 필요했다.
(꼭 RBT가 적당히 대충하는 트리라는 것을 기억하고 넘어가자.)

RBT의 특징
1. AVL보다는 느슨한 기준
2. 높이 균형보다는 색상으로 제한을 둠
3. 삽입 삭제 할 때 회전 횟수 적음
4. 일단 쓰기 쉬움

그러니 AVL보다 쓰기 쉬운 RBT에 대해서 자세하게 알아보자.

RBT의 이상한 점

RBT를 공부하다 보면 어떤 블로그, RBT시각화 사이트, 책등 전부 RBT 모양이 다르다는 것을 알 수 있다.

따라서 공부하다가 혼란이 생길 수 있다

그 이유는 RBT가 규칙만 지켜지면 어떤 모양도 가능하기 때문이다.

RBT의 5가지 규칙

1. 노드는 빨강 또는 검정이다.
2. 루트는 항상 검정이다.
3. 모든 리프노드는 검정이다.
4. 어떤 노드가 빨강이면, 그 자식 노드는 반드시 검정이다.
5. 어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있어야한다.

RBT는 규칙만 지켜진다면 어떤 모양도 허용된다.
즉, RBT는 적당히 대충하지만 규칙만은 확실하게 지키는 친구다.

예시를 통해 이해해보자

              11(B)
            /     \
         9(R)     14(B)
        /   \
     5(B)   10(B)
    /   \
  2(R)  7(R)

이런 트리가 있다. 3을 삽입한다고 생각해보자.

          11(B)
         /     \
      9(B)     14(B)
     /    \
   5(R)   10(B)
  /   \
2(B)  7(B)
   \
   3(R)

이런 트리와

             9(B)
           /     \
        5(R)     11(R)
       /   \     /   \
     2(B)  7(B) 10(B) 14(B)
         \
        3(R)

요런 트리가 나올 수 있다

차이가 발생하는 이유

보수적 색상 조정

최대한 색상만 바꿔서 문제를 해결할려고 하는 것
회전을 마지막 수단으로 여긴다

적극적 회전

규칙 위반이 살짝만 발생해도 바로 회전 회오리
향우 삽입을 고려하고 트리를 균일하게 만들 수 있다

상향식

일단 값을 삽입하고 트리 위쪽으로 올라가면서 규칙 위반을 해결
많은 구현들이 이 방식을 사용 (CLRS)

하향식

삽입과정 중 내려가면서 문제를 미리미리 해결
내려가면서 색을 바꾸거나 회전을 하기도 한다.

이처럼 다양한 방법이 있을 수 있고
RBT트리는 구현 방식에 따라 트리 결과의 차이가 발생할 수 있다

그럼 저걸 다 공부해?

모든 구현 방식을 다 공부할 순 없다

RBT의 두 가지 원칙을 기억하자

규칙이 가장 최우선이다. (규칙은 불변조건이고 어떤 구현 방식이든 규칙을 만족해야 한다.)
규칙을 만족하면 전략을 선택할 수 있다(색상 조정, 회전 전략, 삽입 방식에 따른 차이 등)

우선 따로 공부한 RBT의 방식이 없다면 CLRS의 상향식 구현을 기준으로 삼는 것이 좋다
이유는
1. 가장 많이 쓰이고
2. 설명이 체계적이고
3. 다른 구현들과 비교할 기준이 필요하기 때문이다

RBT

CLRS의 RBT는 상향식 구조이고 보수적 색상 조절 스타일이다
코드를 구현하기 위해 CLRS 기준으로 학습하고자 한다.

RBT 다섯 가지 규칙

노드는 빨강 또는 검정이다.

루트는 항상 검정이다.

모든 리프노드는 검정이다.

어떤 노드가 빨강이면, 그 자식 노드는 반드시 검정이다.

어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있어야한다.

5가지 기준을 꼭 기억하자. RBT의 근본이자 핵심이다.

이건 더 중요하다
4. 어떤 노드가 빨강이면, 그 자식 노드는 반드시 검정이다.
5. 어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있어야한다.

추가 정보

CLRS에서는 꼭 회전을 하고 색상을 변경해야 한다.
코드 구현에서도 중요한 부분이다.

동작 이해하기

우선 RBT는 2가지 동작이 있다
2) Recoloring(색 바꾸기)🎨
3) rotation(회전)🔄

근데 공부를 하려고 인터넷을 키면 Restructuring(재구조화) 개념을 같이 설명한다
이를 이해하고 넘어가자

Restructuring()는 색상을 바꾸고, 회전하고, 포인터를 조정하는 전반적인 과정을 말한다.
다만 우리가 블로그에서 봤던 Restructuring()의 경우는 회전을 의미하는 좁은 의미로 주로 쓰이는 것 같다.

이렇게 용어를 분리했던 이유는 아마 직관적인 이해를 위해서 그런 것으로 생각된다
(회전 + 색상 변경), (색상 변경)의 두 가지의 행동으로 분리해서
직관적으로 (색상 변경) 또는 (회전+색상 변경)의 과정을 설명하려고 했던 것 같다

CLRS에서는 이를 Fix-up 과정으로 되어있다
따라서 용어를 정리하자

Fix-up = Restructuring
Recoloring(색 바꾸기)
rotation(회전)

삽입

삽입은 3단계 과정을 거친다

삽입하는 노드는 항상 RED이다
BST처럼 작은건 왼쪽, 큰건 오른쪽으로 넣는다
규칙 위반을 검사하면서 위로 올라간다

삽입 과정 케이스 (CLRS)

참고: 자식이 없으면 nil 노드로 간주되며, 항상 검정이다.
즉 형제 자식이 없어도 “검정” 상태로 판단한다.

CASE-0
삽입 노드의 부모가 "검정"
끗

🚨문제의 시작은 부모가 RED인 경우 발생🚨

CASE-1 : 부모가 RED, 삼촌도 RED

Recoloring(색 바꾸기)
1. 부모랑 삼촌을 검정으로 바꿔버리고
2. 할아버지는 RED로 바꿔버리기

이어서 할아버지 기준으로 다시 검사 (5가지 규칙)
1. 루트는 항상 검정이다
4. 어떤 노드가 빨강이면, 그 자식 노드는 반드시 검정이다.

-> 할아버지가 루트 노드라면 그냥 검정색으로 바꿔버리면 된다.

잠깐!!!!!!!

CASE-2,3을 하기 위해서는 내부자식, 외부자식을 알아야 한다.

쉽게 이해하면 안쪽으로 들어오면 내부, 밖으로 쭉 나가면 외부자식이다.

반대의 경우도 똑같다.
오른쪽으로 쭉 내려가면 외부자식
부모는 할아버지 오른쪽이지만 자식이 왼쪽으로 가면 내부자식

CASE-2 : 삼촌이 검정, 삼촌의 자식이 내부

CASE-2 = (CASE-3 진입 준비용)

순서
목적 : 내부자식을 외부 자식으로 바꾸기 -> Case-3에서 처리할 수 있는 형태로 변경

회전이라고 하는 이유를 보면

이런 느낌인듯하다.

CASE-3 : : 삼촌이 검정, 삼촌의 자식이 외부

순서
Recoloring(색 바꾸기) + rotation(회전)
1. 부모를 들어올리기 (회전시키기)
2. 부모는 BLACK로 바꾸기
3. 할아버지는 RED로 바꾸기
-> 꼭 회전 이후에 색상 변경하기

이것도 회전이라고 하는 이유를 보면

이런 느낌인듯하다.

삽입 케이스 구분하기

삼촌 노드 색상 확인이 첫 번째 단계

삼촌이 RED → Case 1 (색상 변경)

삼촌이 BLACK → 삽입 위치가 "내부"인지 "외부"인지 판단
내부 자식: 부모 기준 반대 방향 자식 (Case 2)
외부 자식: 부모 기준 같은 방향 자식 (Case 3)

단, 부모가 RED인건 당연하다.
따라서 CASE 1,2,3을 잘 구분해서 사용하자.

삭제😭😭😭😭😭

R.B.T의 최종보스, 악마 그 잡채😈😈😈😈😈😈😈

삭제의 과정 또한 5가지 규칙이 중요하다

1. 노드는 빨강 또는 검정이다.
2. 루트는 항상 검정이다.
3. 모든 리프노드는 검정이다.
4. 어떤 노드가 빨강이면, 그 자식 노드는 반드시 검정이다.
5. 어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있어야한다.

삭제는 규칙 5번 위반이 핵심이다:

어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있어야한다.

삭제의 단계

BST처럼 삭제 대상 노드를 찾고 삭제

자식 0 or 1개면 그냥 삭제

자식이 2개면 → 중위 후계자(successor)랑 교체 후, 후계자를 삭제

삭제 후 균형 복구 (FIXUP)

과정은 BST와 똑같다. 규칙이 어긋나면 고치는 과정만 있을 뿐!
삭제 후 검정 노드 하나가 사라졌을 수도 있음🚨
-> 이게 double-black 문제!🚨🚨🚨🚨🚨🚨🚨🚨🚨![]

근데 double-black이 뭐임

삭제 후 어떤 노드 x가 검정인데, 삭제 때문에 x가 두 개의 검정을 가지는 상태로 간주되는 것
-> 삭제된 노드 색이 RED일 땐 그냥 삭제

이건 현실엔 없고, 논리적인 상태

트리 : 검정이가 부족하다 채워달라.

논리적인 개념이니까 느낌만 보자 느낌만.

4가지 CASE

삽입 처럼 삭제도 4가지 케이스가 있다

기준은 double-black의 형제와 부모이다.
-> 삭제된 노드 색이 RED일 땐 그냥 삭제

CASE-1 : 형제가 빨간색

-> CASE-1번을 진행하면 CASE-2/3/4 중 하나로 구조가 바뀐다.
다음 단계로 넘어가기 위한 단계라고 생각하면 좋겠다.

순서
1. 회전은 형제를 올리고 double-black은 내려가는 방향으로
2. 부모를 빨강으로 만든다
3. 형제를 검정으로 만든다
4. 형제의 반대쪽 자식은 부모의 자식으로 붙게 된다.

아니 근데 저 6은 왜 갑자기 8에 붙어 있다가 5에 쏙 붙어있지?? 저놈은 뭐냐!!!!

Rotate(x) 에 따라 진행되는 것 (이건 그냥 외우자)

회전할 때, 올라가는 노드의 반대쪽 자식은 내려가는 노드의 자식이 된다.
• Right Rotate면 → y의 오른쪽 자식이 x의 왼쪽 자식 됨
• Left Rotate면 → y의 왼쪽 자식이 x의 오른쪽 자식 됨
right Rotate의 경우... 아래와 같다.. 이건 방법이 없다.. 숫자의 크기를 보고 생각해보자.