Krafton Jungle/3. TIL

[WEEK06] RB트리의 삽입/삭제에 대해 우리집 강아지 문식이도 알기 쉽게 설명해줘

munsik22 2025. 4. 19. 17:48

 

🐶 좋아, 문식이도 이해할 수 있게 레드 블랙 트리의 삽입과 삭제에 대해 아주 쉽게 설명해볼게!

🟥⬛ RB트리란?

Red-Black Tree는 스스로 균형을 잡는 이진 탐색 트리야. 트리가 너무 한쪽으로 쏠리면 탐색이 느려지니까, 빨간색(Red)과 검정색(Black)을 이용해 규칙을 정해 균형을 맞추는 트리야.

🌱 문식이도 아는 RB트리 규칙

  1. 각 노드는 빨간색이거나 검정색이다.
  2. 루트 노드는 항상 검정색이다.
  3. 모든 리프(nil)는 검정색이다.
  4. 빨간색 노드의 자식은 반드시 검정색이다. (빨간색끼리 나란히 X)
  5. 어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있다.
🐶 “루트는 까맣고, 빨강이는 까만 애 옆에만 있어야 하고, 길 따라 검은 애 숫자는 같아야 돼!”

🌱 삽입할 때 어떻게 해?

문식아, 새 친구(노드)를 집에 초대한다고 생각해보자. 근데 이 집은 규칙이 엄~청 엄격해!

  1. 먼저 새 친구는 빨간색으로 온다!
  2. 자리에 앉혔는데 규칙을 어기면, 다음 3가지 중 하나를 해줘야 해:

🎨 [Case1] 삼촌이 빨간색일 때 (삼촌 = 부모의 형제)

  • 나도 빨강, 아빠도 빨강이면 혼나!
    👉 아빠랑 삼촌을 검정으로, 할아버지를 빨강으로 바꿔.
    👉 그 다음 할아버지부터 다시 검사해~

🔁 [Case2/3] 삼촌이 검정인데 꼬여있을 때

  • 꼬여 있으면 회전(rotate)해서 모양을 반듯하게 만든다!
  • 회전 후 색을 바꿔서 규칙을 다시 맞춰~
🐶 “새 친구는 빨간 옷 입고 와! 근데 빨강이 둘이 붙어 있으면 혼나니까, 돌리거나 색깔 바꾸는 거야!”
RB_INSERT(tree, new_node):
    1. new_node를 BST 방식으로 삽입한다
    2. new_node의 색을 RED로 설정한다

    3. while new_node의 부모가 RED일 때:
        4. 부모가 할아버지의 왼쪽 자식이면:
            삼촌 = 할아버지의 오른쪽 자식

            if 삼촌이 RED이면:            # Case 1
                부모와 삼촌을 BLACK으로
                할아버지를 RED로
                new_node = 할아버지로 올려보내

            else:
                if new_node가 부모의 오른쪽 자식이면:  # Case 2
                    new_node = 부모로 올리고
                    왼쪽으로 회전(new_node)

                # Case 3
                부모를 BLACK, 할아버지를 RED로
                오른쪽으로 회전(할아버지)

        (오른쪽 자식인 경우는 위 과정을 좌우 반대로)

    5. 루트는 항상 BLACK으로 만든다

🌱 삭제할 때는 어떻게 해?

문식아, 친구 하나가 집에서 나가게 됐어. 근데 검정색 친구가 나가면 균형이 깨질 수 있어. 그럼 나머지 애들이 불편해하겠지?

  1. 검정색 친구가 나가면, 그 빈자리에 ‘추가 검정색’을 붙여서 문제 해결을 시작해.
  2. 이 ‘이중 검정색’을 없애려면 4가지 상황을 봐야 해:

🔥 [Case1] 형이 빨강이다

  • 형을 검정으로, 부모를 빨강으로 바꾼 뒤 회전!
    👉 그럼 문제는 다른 케이스로 바뀌고 다시 검사~

🧤 [Case2] 형이 검정이고, 형의 자식들도 검정

  • 형을 빨강으로 칠해!
    👉 부모에게 이중검정이 생기므로 다시 위로 올라가~

🔄 [Case3/4] 형의 자식 중 하나가 빨강

  • 형을 부모의 색으로 바꾸고, 부모는 검정, 형의 빨간 자식은 검정으로
    👉 그리고 회전하면 OK!
🐶 “검정 친구가 나가면 색깔 맞추는 놀이 시작! 형이 빨강인지, 검정인지 보고 돌리고, 색칠하고… 결국 다 균형 맞추는 거야!”
RB_DELETE(tree, node_to_delete):
    1. node_to_delete를 BST 방식으로 삭제한다
       → 삭제 후 자리에 y가 남고, y의 원래 색이 중요함

    2. 만약 y의 원래 색이 BLACK이라면:
        → 균형이 깨졌으므로 fixup 시작!

        RB_DELETE_FIXUP(tree, x)  # x는 삭제 후 올라온 자식

RB_DELETE_FIXUP(tree, x):
    while x ≠ root and x의 색이 BLACK:
        if x는 부모의 왼쪽 자식이면:
            w = x의 형

            if w의 색이 RED:                     # Case 1
                w를 BLACK, 부모를 RED로
                왼쪽으로 회전(부모)
                w = x의 새 형

            if w의 두 자식이 모두 BLACK이면:   # Case 2
                w를 RED로
                x = 부모로 올려보내

            else:
                if w의 오른쪽 자식이 BLACK이면: # Case 3
                    w의 왼쪽 자식 = BLACK
                    w = RED
                    오른쪽으로 회전(w)
                    w = x의 새 형

                # Case 4
                w의 색 = 부모의 색
                부모와 w의 오른쪽 자식 = BLACK
                왼쪽으로 회전(부모)
                x = root로 설정

        (오른쪽 자식인 경우는 좌우 반대로)

    x = BLACK으로 설정

📝 정리

상황 설명
삽입 “새 친구는 빨강으로 오고, 규칙 어기면 회전하거나 색 바꿔!”
삭제 “검정 친구 나가면, 남은 애들끼리 균형 맞추려고 회전하고 색칠해!”

삽입 Case별 정리

Case 조건 처리 방식 효과
Case 1 부모( 🟥 ), 삼촌( 🟥 ) 부모와 삼촌 → ⬛
할아버지 → 🟥
할아버지를 기준으로 다시 검사		 색상 조정만으로 해결 가능, 위로 전파됨
Case 2 부모( 🟥 ), 삼촌( ⬛ )
내가 삼촌 쪽 방향 자식 (inward)		 부모를 기준으로 회전
(내가 부모와 일직선 되게)		 Case 3로 바꾸기 위한 중간 단계
Case 3 부모( 🟥 ), 삼촌(BLACK)
내가 부모와 일직선 (aligned)		 부모 → ⬛ , 할아버지 → 🟥
할아버지 기준 회전		 색 조정 + 회전으로 문제 해결

삭제 Case별 정리

Case 조건 처리 방식 효과
Case 1 x의 형제(w)가 🟥 w → ⬛, 부모 → 🟥
부모 기준 회전
w를 새 형제로 갱신		 형을 ⬛ 으로 만들어 다음 Case로 이동 가능하게 함
Case 2 w는 ⬛
w의 자식 둘 다 ⬛		 w → 🟥
x = 부모로 올림 (이중 검정 위로 전달)		 색만 바꿔주고 문제를 부모에게 위임함
Case 3 w는 ⬛
w의 왼쪽 자식 🟥
w의 오른쪽 자식 ⬛		 w → 🟥
w의 왼쪽 자식 → ⬛
w 기준으로 오른쪽 회전		 Case 4로 바꾸기 위한 중간 단계
Case 4 w는 ⬛
w의 오른쪽 자식 🟥		 w의 색 → 부모의 색
부모, w의 오른쪽 자식 → ⬛
부모 기준 왼쪽 회전		 최종 회전으로 이중 검정 해소, 종료