개요

Red Black Tree.
1978년 레오 귀바스, 로버트 세지윅이란 사람들이 만들어낸 자료구조이다.
기본적으로는 자료구조이기는 한데, 연산 절차와 과정이 존재하니 알고리즘이라고 불러도 이질감은 느껴지지 않는 듯..

자가 균형 이진 탐색 트리의 한 일종이다.
즉, 이진 탐색 트리이기는 한데 어느 쪽으로 지나치게 편향되지 않도록 알아서 구조가 조정되는 트리라는 것이다.

이 친구는 현재 삽입, 조회 등의 작업이 가장 효율적이라고 평가된다.
그래서 각종 프로그래밍 언어에서 사용되는 정렬이나 연관 배열에서 내부적으로 사용되고 있다.

자가 균형 이진 탐색 트리?

이 부분은 사실 나중에 문서를 따로 파는 게 맞다.
avl 트리 같은 것들도 존재하기에 그렇다.
그러나 지금은 여기에 간단하게 쪽글만 남긴다.

일단 트리라는 것은 그래프의 일종으로, 사이클이 발생하지 않는 그래프의 관계이다.
구체적인 정의는 방향성이 있는 비순환 그래프(DAG).
그래서 부모와 자식 관계로 노드들이 이어진다.
이중에서 이진 트리는 자식을 2개 이하만 가지는 트리를 말한다.

그리고 이진탐색트리는 이진 트리 중에서 다음의 속성을 만족하는 트리를 말한다.

• 왼쪽 서브 트리는 특정 노드보다 작다.
• 오른쪽 서브 트리는 특정 노드보다 크다.
• 이 조건을 모든 트리 내 모든 구간에서 만족한다.

단순하게는 정렬된 이진 트리라고 할 수 있겠다.
이 트리 구조는 원하는 값을 매우 빠르게 찾을 수 있다는 장점을 가진다.
위 그림의 데이터들이 그냥 배열로 나열된 상태일 때 10을 찾기 위해서는 처음부터 한 값씩 비교를 해나가야 할 것이다.
그러나 이 트리에서는 일단 루트 노드인 6에서 시작한다.
이후 찾으려는 10은 6보다 크기에 6의 오른쪽 자식으로 간다.
오른쪽 자식인 8보다 10이 또 크니까 또 오른쪽으로 간다.
그럼 찾을 수 있다!
그래서 시간 복잡도는 O(log n)으로 찾을 수 있게 된다.

그러나 이 트리는 사실 다양한 모양을 가질 수 있는데...

극단적으로 트리를 만들 때 잘못 만들면 이렇게도 만들어진다.
분명 방금 말한 조건은 충족하지만 트리의 깊이가 너무 깊어졌다.
이래서는 조회를 할 때 좋은 효율이 나올 수가 없게 된다.

그래서 이런 식으로, 최대한 루트 노드로부터 리프 노드까지 가는 길이 최소화되도록 균형을 잡는 것이 중요하다.
이렇게 구조를 짜게 되면 조회, 삽입 등의 성능을 최적화할 수 있다.
이렇게 균형을 잡는 과정에 대한 알고리즘이 자가 균형 과정인 것이고, 레드블랙트리는 이러한 자가 균형 과정을 가진 이진탐색트리라는 것.

구조

도대체 어떻게 균형을 맞춘다는 것일까?
균형을 맞추는 과정은 삽입과 삭제 과정에서 일어난다.
이를 위해 어떤 구조로 레드블랙트리가 생겨먹었는지 보자.
이 부분을 머리에 계속 꿰고 있어야 본격적인 알고리즘 절차를 이해할 수가 있다.

이 그림이 레드블랙 트리의 예시이다.
그냥 노드들에다가 검은색, 빨간색으로 색깔놀이 해둔 것.
그렇다고 아무렇게나 색깔을 배치하는 것은 아니다!
이 색깔들은 특정한 원칙을 준수하는 채로 배치된 것이고, 이 원칙을 준수하기 위해 일련의 동작을 거치다보면 자연스레 균형이 맞춰진다는 것이 레드블랙트리의 핵심이다.

원소

기본적으로는 크게 3가지의 원소가 있다.

• 블랙 노드
  • 말 그대로 검은색
• 레드 노드
  • 말 그대로 빨간색
  • 나중에 블랙 노드에서 검은색을 빼는 식의 과정이 일어나는데, 블랙에서 블랙을 뺀 색은 레드라고 간주한다.
  • 직관적이진 않을 수 있겠으나.. 그렇게 생각하면 이해가 편하다.
• NIL
  • 아무것도 없는 노드로, 균형을 위해 도입된 가상의 노드
  • 위의 사진처럼 모든 리프노드 뒤에 위치만 차지하는 노드로, 레드블랙트리에서는 이 놈이 리프노드 역할을 해준다.
  • 이 노드는 값이 없기는 하나, 일단 검은색으로 간주한다.
    • 이렇게 이해해야 삭제 과정을 설명하는 게 쉬워진다.

속성

레드블랙트리는 다음의 속성을 꼭 지녀야 한다.
이 속성을 지니기 위해 각종 절차가 일어나는데, 이 과정으로 균형이 맞춰진다.

1. 노드는 레드 혹은 블랙이다.
2. 루트 노드는 블랙이다.
3. 리프 노드(NIL)는 블랙이다.
4. 레드 노드의 자식은 무조건 블랙이다.
5. 어떤 노드에서 시작하여 하위 리프로 가는 모든 경로는 같은 개수의 블랙 노드가 있다.
   1. 이건 부연이 필요해서 붙인다.
   2. 가령 위의 사진에서 루트 노드인 13에서 모든 리프 노드로 가는 경로를 보라.
   3. 루트 노드 자신을 포함해서 블랙 노드의 개수는 전부 2개로 동일하다.

1부터 3 속성은 아주 단순하다.
그러나 4,5번 속성이 매우 까다로운 조건으로 이것들이 지켜지는 게 핵심이다.
5번 속성으로 도출되는 검은 색 경로의 길이를 black height라고 부른다.

특징

위의 속성들을 토대로 나오게 되는 몇 가지 특징이 있다.
대충 내가 해석해낸 인사이트들이 섞여 있는데, 이것들이 레드블랙트리를 이해하는 통찰점이라 생각한다.
그냥 머리가 좋으신 분이라면 굳이 이렇게 특징지어 생각하지 않아도 딱 와닿을 수도 있겠다.

루트 노드로부터 가장 먼 리프와의 거리와 가장 가까운 리프와의 거리는 항상 2배 이하

그림에서 sub는 레드블랙트리 중 2번 속성만 만족하지 않는 서브 트리라 봐주면 되겠다.
4와 5 속성을 생각해보면 당연하다.
일단 5번 때문에 가는 경로의 블랙은 전부 똑같다.
가장 가까운 리프 거리는 그 경로가 전부 블랙일 것이다.
가장 먼 리프는 중간에 최대한 많이 레드가 낄 것이다.
근데 4번 속성에 의해 레드 다음에는 무조건 블랙이라, 아무리 레드가 많이 껴도 블랙의 2배 이상으로 낄 수는 없다.

이래서 완벽하진 않지만(완벽한 균형은 AVL 트리) 개략적으로 균형(roughly balanced)이 만족되는 상태이다.

이론적으로는 블랙 노드로만 채워진 레드블랙트리 가능

4번 속성 때문에 레드로만 채워진 레드블랙트리는 불가능하다.
하지만 이론적으로 모두 블랙인 건 가능하다.
나중에 삽입 과정을 보면 절대 그런 상황은 나오진 않긴 한다.
이걸 통해 레드 수가 적을 수밖에 없다는 것, 그리고 레드는 있다가 사라져도 아무런 영향이 없다는 것을 알 수 있다.

레드 부모와 블랙 자식 색 바꾸기

레드블랙트리의 일부분을 떼어놓고 보자면, 이렇게 색깔을 바꾸는 것이 가능하다.
그냥 아래 있던 블랙이 위로 합쳐진 형태라고도 보면 5번 속성을 위배하지 않는 것을 알 수 있다.

이런 걱정이 있을 수 있다.
위 경우에서는 네모 칸은 색을 바꿨다가는 레드 자식 아래 레드라서 4번 속성 위배다!
맞다.
그래서 이것은 자식들의 자식들이 블랙일 때만 가능하다.

한편 블랙 부모와 레드 자식의 색을 바꾸는 것도 가능하다.
물론 이것도 부모의 부모가 블랙일 때만 가능하다.

동작 매커니즘

이제 본격적으로 어떻게 레드블랙트리가 균형을 맞추는 작업을 하는지 볼 것이다.
잠깐 언급했지만 균형화 작업은 삽입과 삭제에서 발생한다.

일단 다음의 삽입이든 삭제든 다음의 순서를 따른다.

1. 이진 탐색 트리 방식으로 삽입, 혹은 삭제를 한다.
2. 하고 보니까 레드블랙트리의 속성이 위배되니까, 이를 맞추는 작업을 한다.
3. 맞추다보니 균형 정상화! 신창섭 그는 대체

여기에서 2번 동작이 세부적으로 들어가보면 참 어렵다..
그래서 삽입과 삭제 각각을 따로 볼 것이다.

들어가기에 앞서 몇가지 숙지할 동작이 있다.

이진 탐색 트리의 삽입과 삭제

삽입은 그냥 루트에서 시작해서 분기를 타고 들어가다가 리프까지 가면 그 자리에 쏙 들어가는 방식이다.
어렵지 않아 부연하지 않는다.

삭제는 successor, 혹은 presedessor를 이용한다.
successor란 각 노드마다 성립하는 개념으로, 자신의 바로 이전 값을 말한다.
presedessor는 바로 다음 값이며, 크게 차이 없으므로 이제부터는 successor만 기준으로 설명하겠다.

여기에서 6의 successor는 5다.
8의 successor는 7이다.
대충 보면 알겠지만, 결국 한 노드의 successor는 자신의 왼쪽 서브트리에서 가장 오른쪽에 있는 리프노드이다.
그림으로 봤을 때는 그냥 x축이 왼쪽에서 가장 가까운 값이라고도 할 수 있겠다.
한 노드의 삭제는 이 successor와 위치를 바꾼 후 이뤄진다.

위의 예시에서 6을 삭제할 때는 이렇게 6의 successor인 5와 위치를 바꿔 6을 리프노드로 옮긴 다음, 삭제해버리면 된다!
자신의 바로 이전 값이라 이렇게 바꿔도 아무런 문제가 발생하지 않는다.

successor가 없는 리프노드나, 자식이 하나인 노드는?
리프노드면 위에서처럼 그냥 삭제해버리면 되고, 자식이 하나라면 그냥 그 자식을 위로 올려주면 되니 부연하지 않겠다.

회전

회전이란 부모 노드와 자식 노드의 위치를 바꾸는 동작이다.
왼쪽, 오른쪽 회전이 있는데 실질적인 매커니즘은 같으니 오른쪽(시계방향)으로 회전하는 동작만 예시로 쓰겠다.
이게 균형화를 하는 작업의 코어라고 할 수 있다.

그림으로 보는 게 가장 편하다.
이 상태에서 네모칸을 회전을 시키고 싶다.
즉, 3이 부모가 되고 6이 자식이 되게 하고 싶다.

요런 식으로 말이다!
근데 이러니까 이진 트리가 아니게 되어버린다..
저 초록 박스가 문제인데, 이건 부모였다가 졸지에 자식이 되어버린 6이 가져가면 된다.
자식이었던 놈이 부모가 돼서 자식 자리가 하나 비었으니 거기에 쏙 넣어주면 된다.

이런 식으로 말이다.

이러한 회전 동작은 이진탐색트리의 조건을 깨지 않는다.
(위의 사진은 대충 그리다가 5의 위치가 조금 잘못되긴 했는데 암튼)

삽입

이제 진짜 진짜 본격적으로 들어가보자!
위에서 이야기한 매커니즘을 조금 더 구체화하면 이렇다.

1. 이진 탐색 트리 방식으로 레드 노드를 삽입한다.
   1. 이래서 이론적으로만 전체 블랙 트리가 가능한 것이다.
2. 레드블랙트리 속성을 맞추기 위한 작업을 한다.
3. 맞추다보니 균형 정상화!

1번을 수행하게 되면 어떤 상황들이 나올 수 있을까?
레드블랙트리는 삽입 과정에서 삽입 노드(Node)와 그의 부모(Parent), 조부모(Grandparent), 삼촌(Uncle)을 본다.

이런 식으로 말이다.
이게 회전을 시키다보면 실제 관계는 바뀌게 되는데 여기에서는 처음에 매겨진 상태의 관계를 토대로 각 노드를 언급할 것이다.
즉 회전해서 조부모가 부모의 자식이 되도 그냥 조부모라 부른다는 것.
또한 중간에 재귀를 해서 위로 거슬러 올라가는 경우가 생긴다.
가령 삽입 노드의 조부모인 G가 아래 보게 될 동작들을 수행하게 되는 경우 말이다.
이때는 G를 N으로 치고 이야기하게 될 것이다.

그럼 이제 구체적으로 2번에서 발생하는 경우와 이에 대한 동작들을 보겠다.
각 경우를 합치면 레드블랙트리에서 발생할 수 있는 전체 상황을 보여준다.

1. N이 루트

일단 레드 노드로 삽입했는데 루트 노드였다!
그러면 2번 속성에 따라 블랙 노드로 바꾸면 끝이다.
참고로 nil 노드는 귀찮으면 그냥 표시 안 하고 있는데, 다 기본적으로 nil은 있는 것이다.

2. N의 부모가 블랙

부모가 블랙이면 그 아래 레드가 삽입되도 아무런 문제가 없다.
레드는 5번 속성에 아무런 영향을 끼치지 않기 때문이다.
그래서 그냥 넘어간다.

3. N의 부모는 레드, 삼촌도 레드

넣고 보니 4번 속성이 충족되지 않아 문제가 발생한다.
참고로 이 상황이라면 무조건 조부모는 블랙일 수밖에 없다.
이때 취하는 동작은 간단하다.

그냥 이렇게 부모, 삼촌, 조부모의 색을 바꿔버린다.
[[#레드 부모와 블랙 자식 색 바꾸기]]가 가능하기 때문이다.

그러나 이렇게 하면 G의 부모가 레드일 때 문제가 발생한다!
그러면 그 문제를 G한테 짬때린다.
코드적으로는 재귀를 시키는 것이다.
위 사진에서는 G가 지금 이 3번 케이스에 해당하게 된 것이 보인다.
그러니 이때부터 G를 N으로 잡고 관계를 다시 설정하여 이 로직을 돌린다는 것이다.
3번이니 이 놈도 결국 지 조부모한테 문제를 짬 때릴 것이다.
그러다 보면 1번, 2번 케이스를 결국 만날 테고, 상황은 종료된다.

4. N의 부모는 레드, 삼촌은 블랙, 그러면서 N은 오른쪽

점점 조건이 구질구질해지는 게 느껴진다..
이제는 오른쪽인지 왼쪽인지도 따진다..

아무튼 지금까지는 색깔 놀이만 했지 실질적으로 균형 작업은 일어나지 않았다.
그러나 이 상황에서는 진짜로 균형 작업이 들어가게 된다.

이 상황이 되면 문제를 다음으로 넘긴다.
다음은 짐작하겠지만 삽입되니 왼쪽이더라 케이스인데, 이렇게 하기 위해서는 회전을 사용한다.

반시계 방향으로로 회전을 시켰다.
이제 부모 노드가 아래로 갔는데, 이 놈 입장에서 다음의 상황이 되었다.

참고로 3번의 상황에서 삽입 조치는 위로 전파되는 것을 보았다.
즉 위에서도 이런 문제가 발생하면 이러한 대응을 한다.
그래서 nil노드로 표시된 부분들이 실제로는 서브 트리가 될 수도 있다는 점을 명심하자.
(어차피 이미 레드블랙트리를 만족하고 있는 상태라 쟤네들한테 달리 발생하는 이슈는 없다.)

어차피 이 동작에서는 검은 노드의 개수가 늘어난 것 없이 레드만 가지고 놀았기에 5번 속성이 위배되는 사항은 없다.

5. N의 부모는 레드, 삼촌은 블랙, 그러면서 N은 왼쪽

처음부터 이 상황이었을 수도 있고, 4번에서 동작을 해서 넘어왔을 수도 있고.
아니면 3번 경우로 아랫노드한테 짬맞아서 이럴 수도 있다.
암튼 이게 마지막이다!

이때도 회전을 한다.
근데 이번에는 색도 바꾸면서 회전한다.

일단 부모를 시계로 회전시킨다!
그런데 이번에는 4번과 다르게 블랙과 레드가 회전의 대상이 되어 5번 속성에 문제가 생길 여지가 있다.

이러면 어떤 문제가 발생할 수 하는가?

• N의 서브 트리들은 블랙이던 조부모(G)가 없어져서 black height가 1 줄었다.
• U 쪽 입장에선 갑자기 지네 위에 빨간색이 하나 추가된 거라 크게 차이는 없다.
• P에 붙어있다가 갑자기 G에 붙어버린 초록 박스 역시 결국 블랙 개수의 변동은 없어서 문제 없다.

이 상황에서 해결책은, N 측에는 블랙을 하나 추가시켜주며 동시에 G 측에는 문제가 없게 하는 것이다.

이렇게 말이다.
즉, 부모와 조부모의 색깔을 바꿔버리면 부모의 왼쪽 서브트리는 블랙이 하나 늘어나고 오른쪽은 그대로라 5번 속성을 충족할 수 있다.
이 과정에서 결국 자연스럽게 4번 속성도 해결이 된 것이 보인다!

이 과정은 과연 트리를 균형있게 만든 걸까?
레드블랙트리의 특징으로서, 러프하게는 균형을 이루었다도 말할 수 있다.

삭제

이번에는 삭제를 보겠다.
삭제는 더 어렵다..

1. 이진 탐색 트리 방식으로 노드를 삭제한다.
2. 레드블랙트리 속성을 맞추기 위한 작업을 한다.
3. 맞추다보니 균형 정상화!

핵심 - 우리가 신경 쓸 것은 블랙 노드의 삭제

여기에서 먼저 주목할 사실이 하나 있다.
이진 탐색 트리로 노드를 삭제하면 해당 노드는 무조건 자식을 최대 하나밖에 가질 수 없다는 것이다.

이렇게 생긴 이진탐색트리의에서 6의 successor는 5이다.
6의 successor인 5에게 오른쪽 자식(가령 5.5)이 있었다면, 그 녀석이 6의 successor가 될 것이다.
왼쪽으로는 붙으나마나이긴 하지만 successor의 오른쪽 자식, 파란 박스는 항상 비어있다는 것이다.

이것 덕분에 사실 삭제가 진행될 때 나올 수 있는 경우의 수는 매우 한정된다.

이진탐색트리 삭제 방식에 따라 지워지기로 결정된 노드 N에 대해서 이렇게 3가지 상황만 나온다.
N이 레드이면 아래는 전부 NIL이다.
4번 속성을 어기지 않으며 한쪽에 뭐가 더 붙으려면 무조건 블랙이 붙는데, 그러면 5번 속성이 만족이 안 돼서 불가능.
N이 블랙이어도 결국 4,5번 속성을 지키려면 위 경우밖에 나오지 않는다.
각 상태에서 N을 삭제한다면 어떤 모습이 될까?
(참고로 3번째 경우 N을 삭제하면 이진탐색트리가 그러하듯 레드 노드를 N 자리에 둔다.)

없어진 자리는 항상 NIL로 채운다.
초록 원은 여기에 블랙 노드가 사라진 자리에 extra black이라는 것을 부여한 것을 나타낸다.
이것을 통해 이중 블랙과, 레드앤블랙 노드가 성립하게 된다.

• 레드 노드
  • 그냥 지워져도 상관 없다.
  • 그래서 그냥 NIL로만 남는다.
• 블랙 노드
  • NIL 노드가 되었을 때, 여기에 extra black을 부여해 이중 블랙(double black)으로 만든다.
  • NIL은 블랙으로 간주하기에 이렇게 표현한다.
• 블랙을 지웠더니 아래에서 레드 노드가 올라옴
  • 블랙 노드가 지워진 자리를 꿰찬 레드 노드에 extra black을 부여해 레드앤블랙(red and black)으로 만들었다.
  • 근데 레드앤블랙은 그냥 블랙으로 바꿔버리면 문제가 해결된다.
    
    이 사진을 보면 알 수 있듯이, N이 사라지는 순간 N의 서브트리의 black height는 다른 영역보다 1이 줄어든다.
    블랙 노드가 사라지면 무조건 5번 속성이 위배되는 일이 발생하기에, 이를 나타내고자 extra black을 사용하는 것이다.

내가 처음 본 영상에서 이 extra black이란 개념을 써서 알려주다 보니 나중에 다른 글들을 볼 때 엄청 혼란스러웠다.
그래서 이렇게 길게 설명했는데, 이제부터는 본격적으로 알고리즘을 설명할 때부터는 이 개념은 언급하지 않고 진행하고자 한다.
다만 이걸 표현해주는 게 가시성은 좋아서 black height가 하나 부족한 서브 트리의 최상단에는 초록 원 표시를 넣겠다.
결국 중요한 건 꺾이지 않는 블랙 블랙이 삭제되면 발생하는 문제를 해결해야 한다는 것이다.

그래서 이제부터! 드디어! 레드블랙트리에서 나누는 갖가지 경우들을 살펴보자!
삭제 과정에서 레드블랙트리는 다음의 노드들을 살펴본다.

삭제되는 노드(Node), 그의 부모(Parent), 삭제 노드의 형제(Sibling), 그리고 형제의 자식 노드(Sibling Left, Sibling Right)이다.
삽입에서 봤듯이 삭제 쪽에서도 재귀를 거치는 과정이 있는데, 이때도 똑같이 대상이 되는 놈을 N으로 잡고 이야기하겠다.

1. N이 루트

뭘 더 할 게 없다.
재귀를 타고 올라온 상황이더라도 마찬가지이다.
어차피 N의 서브트리 자체 내에서는 항상 레드블랙트리 속성을 만족하는 게 보장된다.

2. S는 레드

P가 어떻든, SL,SR이 어떻든 형제가 레드면 여기에서 일단 조치를 취한다.

이런 상황이면 삽입의 4번 경우처럼 다른 상황으로 만드는 방식으로 해결한다.
어떻게 만드느냐, 부모를 레드로 만드는 것이다!

일단 반시계로 회전시킨다.
그냥 이렇게 하면 갑자기 SR은 부모에 위치했던 블랙이 하나 사라지게 된다.

이 상태에서 형제와 부모의 색을 바꿔만 주면 SR의 문제는 해결된다.
아직 주 관심사인 N의 문제는 전혀 해결되지 않았으며, 이후 보게 될 4,5,6 케이스 중에 하나로 해결을 하게 된다.

3. S는 블랙, 나머지도 다 블랙

2번을 통해 만들어질 수는 없는 케이스.
2번의 동작이 실행되면 무조건 P가 레드가 되기 때문이다.

이런 상황이면 S를 레드로 만들어버린다.
그렇게 되면 S 쪽도 블랙이 하나 부족해지는 상황이 되므로, 통합해서 보자면 P의 서브트리 전체가 black height가 하나 부족한 상태가 된다.

이러면 이때부터는 P가 모든 책임을 지고 또 재귀로 타고 올라가면서 문제를 해결하면 된다.

대충 이런 상태가 돼서 2번 동작을 할 수도 있고, 아니면 또 전부 블랙이라 다시 3번 동작을 할 수도 있고.
P가 루트였다면 거기에서 상황은 종료다.
아무튼 위로 떠넘기는 방식으로 해결한다.

4. S는 블랙, SR과 SL은 블랙인데 P만 레드

쉽게 말해 그냥 P만 레드인 상황.
1번 경우와 더불어 가장 쉽게 끝나는 케이스이다.
SL, SR의 값은 중요하지 않다.

우리는 N이 없어지며 줄어든 black height를 맞춰주기만 하면 된다.
그러면서 S쪽은 그대로 유지를 시켜야 한다.
그럼 단순히 여기에서 부모와 형제의 색만 바꿔주면 끝난다.

이렇게 말이다.
자연스레 N쪽에서 발생했던 5번 속성이 해결된다.

5. S는 블랙, SR은 블랙, SL가 레드

SL과 SR에 레드가 끼는 순간부터는 P는 더 이상 중요하지 않다.

파란색은 그냥 뭐여도 상관 없다는 뜻에서 넣은 색이다.
이 경우에는 조금의 동작으로 마지막인 6번의 상황으로 만들어 넘긴다.

서브트리들은 대충 있을 것이라 생각하고 보면 되겠다.

6. S는 블랙, SR이 레드

드디어 마지막!
3번 경우부터 시작해서 계속 조건 분기를 줄여가며 진행되는 것이 보인다.
여기도 마찬가지로 P, SL의 값은 중요하지 않다.

이번에도 시계 반대 방향으로 회전시킨다.

이 상황에서는 상관없다는 값들 때문에 경우를 조금 나눠서 생각해야 하는데, 결국 해야할 조치는 똑같다.

• P가 블랙이었을 경우
  • N은 부모 라인에 블랙인 S가 추가돼서 블랙이 하나 늘었다.
  • SL에는 위에 P와 S가 지나가기에 변화가 없다.
  • SR은 값이 하나 부족해졌다.
  • 그러므로 SR을 블랙으로 만든다.
  • 어차피 P와 S는 둘 다 블랙이기에 서로 색을 바꿔도 상관 없다.
• P가 레드였을 경우
  • N은 부모 라인에 블랙인 S가 추가돼서 블랙이 하나 늘었다.
  • SL에는 위에 P와 S가 지나가기에 변화가 없다.
  • SR에는 변화가 없다.
  • SR을 블랙으로 만들어본다.
  • P와 S의 색을 바꾸면 SR을 바꿔도 아무런 상관이 없다.

즉, SR을 블랙으로 만들고 S와 P의 색을 바꾸면 문제가 해결된다는 것이다.
특히 P가 레드인 것은 [[#레드 부모와 블랙 자식 색 바꾸기]] 경우라 더 직관적이다.

분석

길고 긴 과정이었다..
다른 것도 그렇지만 레드블랙트리는 특히나 구현보다 이 원리 자체를 이해하는 것이 중요하다.
여태까지 왼쪽의 노드를 삽입하거나 삭제하는 것을 기준으로 설명했으나, 오른쪽이라면 그대로 반대로만 해주면 된다.

레드블랙트리는 왜 빠를까?

조회

위에서 봤듯이 레드블랙트리는 얼추 균형이 맞는다.
상황에 따라 다를 수는 있겠지만 아무리 그래도 루트에서 가장 먼 거리와 짧은 거리는 2배 이상 차이가 나지는 않기에 일반 이진탐색트리보다는 훨씬 유용하다.

삽입, 삭제

시간복잡도에 가장 큰 영향을 끼치는 것은 재귀이다.
그런데 레드블랙트리는 삽입과 삭제에서 매우 특정한 상황에서만 재귀를 들어가게 된다.
그리고 그 재귀는 결국 루트 노드를 찾아가는 과정이기 때문에 O(logn)이다.
결국 레드블랙트리의 균형화 작업은 회전할 때만 값들의 변동이 일어난다.
그리고 이 작업은 많이 일어나지 않는다.

참고

• 위키
  • https://ko.wikipedia.org/wiki/레드-블랙_트리
• 유툽
  • https://youtu.be/6drLl777k-E?si=qwwdoSaRg81yMS9X