Red-Black Tree (RB 트리) | 삭제 연산

RB 트리의 삽입 연산에 이어 삭제 연산 !

 

RB트리의 연산을 이해할 때는 색깔이라는 속성이 특정 노드에 귀속적인 게 아니라, 자유롭게 날아갈 수도 있는 속성임을 이해하는게 중요하다. 색깔은 말 그대로 노드의 구조를 파악하고 컨트롤하기 위해 붙여놓은 인덱스같은 거다. 

색깔을 붙인 것도 우리 마음대로였고, 색깔을 바꾸거나 하는 것도 RB트리의 속성 유지에 도움이 된다면 아무렇게나 해도 된다.

그저 약속일 뿐이다. 우리가 배우는 방법론은 그 중 효율적인 방법일 뿐이다. 

 

바로 들어가기에 앞서 RB 트리의 5가지 속성을 다시 복기하자: 

1. 모든 노드의 색은 red 또는 black 이다.
2. 루트 노드는 black이다.
3. nil 노드는 black이다.
   • nil 노드: null과 통하는 의미라고 생각하면 된다. 특정 노드가 왼쪽, 오른쪽, 혹은 양쪽에 자식 노드가 없을 때, 그 자식 노드의 빈 자리를 일단 nil 노드로 채운다. 값이 있는 노드와 동등하게 취급한다.
   • RB 트리에만 존재하는 개념으로, RB 트리에서 리프 노드는 항상 nil노드이다. 즉, 바닥은 값이 없는 nil 노드로 깔려있어야한다.
4. red 노드는 black 자식 노드만을 가져야 한다. 즉, red 노드는 연속되지 않는다. 
5. 임의의 노드에서 모든 리프(nil) 노드까지 가는 경로에 있는 black의 수는 동일해야 한다. (이때 자기자신은 카운트에서 제외)
   • 아무 노드나 잡고 리프 노드까지 가는 모든 경우의 수를 따져봤을 때 이 조건이 만족해야 한다.
   • 여기서 말하는 black의 수를 '노드 x의 black height'라고 부른다.
     • ex) 아래 이미지에서 '20' 값을 지닌 노드의 black height는 2이다. 

 

삭제 연산에선 extra black 등 새로운 개념이 등장하고, 앞에서 배웠던 #5의 추가 속성(부모 자식 색을 바꿔도 #5 속성은 유지된다.)과 회전 개념도 다시 등장한다. 

---

삭제 연산

전반적인 과정은 다음과 같다.

0. 가정: 삭제 전 RB 트리 속성 만족한 상태
1. 삭제: BST와 동일
2. 삭제 후: RB 트리 속성 위반 여부 확인
3. 재조정: 속성을 위반했다면, 각 case에 맞춰서 재조정

 

우선, 삭제 자체는 BST와 동일하게 수행된다.

1. 삭제하려는 노드 찾기
2. 삭제 노드의 자식이 0 또는 1개인 경우: 부모의 포인터를 자식에게 연결
3. 삭제 노드의 자식이 2개인 경우: 후계자와 대체
   1. 삭제 노드의 위치와 색깔은 후계자가 그대로 물려받는다. 

 

RB 속성 위반 검사

1. 삭제되는 색 파악 (자녀 노드 개수 체크 -> 필요시 후계자 체크)

 

RB 트리에서 노드를 삭제할 때, 삭제되는 색을 통해 RB 속성 위반 여부를 확인할 때 매우 중요하다.

BST의 삭제 연산 논리를 그대로 따르면 삭제되는 색도 당연히 알 수 있게 된다.

 

1) 삭제 노드의 자녀 노드가 0 또는 1개

• 삭제되는 색 = 삭제되는 노드의 색 (여기서 nil 노드는 자녀로 안 침)

 

• 여기선 10, 25, 37, 40, 80이 해당된다.
  • 10 삭제시 black 삭제, 25 삭제시 red 삭제, 80 삭제시 black 삭제, 40 삭제시 black 삭제

 

2) 삭제 노드의 자녀 노드가 2개

• 삭제되는 색 = 삭제되는 노드 후계자(successor)의 색
• 20 삭제시 red(25의 색) 삭제, 35 삭제시 red(37의 색) 삭제, 50 삭제시 black(80의 색) 삭제

 

2. 속성 위반 여부 확인

만일 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.

만일 삭제되는 색이 Black 이라면, #2 #4 #5 속성을 위반할 수 있다.

 

위 케이스에서 40값 노드를 삭제하면 #4, #5 속성을 위반하게 된다. (red 연속, black height 어긋남)

루트 노드인 35값 노드를 삭제하면 #2 속성을 위반하게 된다. (루트노드가 red)

 

 

결국, 삭제되는 색이 black일 경우에 재조정 작업을 거치면 된다. 

 

재조정

#2를 위반했을 경우 (루트노드 black)

• 루트 노드를 black으로 바꿔준다. 끝!

 

#4를 위반했을 경우

삭제에서는 #4 위반이 발생할 일이 거의 드물며, 발생했다면 #5가 위반된 상황일 것이다.

따라서 #5를 해결하는 과정에서 #4도 함께 해결된다.

 

#5를 위반했을 경우 (black height 어긋남) (#4도 여기서 해결)

삭제되는 색이 black일 때 가장 흔하게 위반되는 속성이다. 

삽입 연산에서는 #4가 골칫거리였다면, 삭제 연산에서는 #5 속성이 골칫거리다. 

 

여기서는 extra black이라는 개념이 도입된다. 

- extra black: 경로에서 black 수를 카운트할 때, extra black은 하나의 black으로 카운트된다. 
- double black: extra black이 부여된 black 노드. 따라서 black 2개로 카운트된다.
- red-and-black: extra black이 부여된 red 노드. 따라서 black 1개로 카운트된다.

 

#5 속성 재조정은 extra black을 부여하고, extra black을 회수하는 과정이다. 문제는 회수에서 케이스가 많다는 것...

 

재조정 방법

1. 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다. 
   • 아마 자식 노드 or nil 노드가 대체했을 것이다. 그게 무엇이든, 해당 노드에 extra black을 부여한다.
   • 만일 대체한 노드가 이미 black이라면, 해당 노드는 double black이 된다. 
   • 만일 대체한 노드가 red라면, 해당 노드는 red-and-black이 되어 black 1개로 카운트된다.
2. extra black을 회수한다. (double black 또는 red-and-black을 적절한 상태로 돌린다.)
   • red-and-black: 그냥 black으로 만든다. 
     • 이 경우, #4가 위반되었던 상황이라면 #4도 자동으로 함께 해결된다.
       (red였던게 black이 되는 거니까, 연속 red여서 문제였다면 당연히 같이 해결됨)
   • double black: double black을 해소하는 상황이 삭제 연산의 꽃이라고 할 수 있다. 4가지 케이스로 분류된다.
     (기준: double black 형제의 색 + 형제의 자녀들의 색) 
     1. case 4: 더블 블랙의 형제가 black + 형제의 오른쪽 자녀가 red 인 경우
        1. 형제 노드는 부모 노드의 색을 물려받는다. 
        2. 부모 & 형제의 오른쪽 자식 노드는 검은색으로 바꾼다.
        3. 부모 노드를 기준으로 좌회전한다. 
     2. case 3: 더블 블랙의 형제가 black + 형제의 왼쪽 자녀는 red, 오른쪽 자녀는 black인 경우
        1. 형제와 형제의 왼쪽 자녀를 color flip한다.
        2. 형제 기준으로 우회전한다.
        3. 이제 case 4와 동일한 상태이다. 
     3. case 2: 더블 블랙의 형제가 black + 형제의 두 자녀가 모두 black인 경우
        1. 더블 블랙의 extra black과 형제의 black을 모아서 부모 노드에게 전달한다.
        2. 그럼 부모는 red-and-black 또는 double black이 된다.
           1. 이로써 기존의 double black인 A는 해소가 됐다. 
        3. 이제 extra black이 부모에게 옮겨갔다. 이 경우 3가지 case로 나뉜다. 
           1. 부모가 red-and-black 일 경우 -> black으로 바꿔서 해결
           2. 부모가 루트 노드일 경우 -> black으로 바꿔서 해결
           3. 부모가 더블 블랙이고 루트 노드가 아니라면 -> 부모 노드의 관점에서 다시 double black 해소 시작 (case 1, 2, 3, 4)
     4. case 1: 더블 블랙의 형제가 red인 경우
        1. 부모와 형제를 color flip 한다.
        2. 부모 기준으로 좌회전한다.
        3. 이제 case 2, 3, 4 중에 하나와 같은 상황이다.

모든 상황은 오른쪽 -> 왼쪽으로 바꾸면 대칭적으로 성립된다. 

 

 

extra black 부여

우선 extra black을 부여한다는 게 뭔지를 먼저 이해해보자. 

만일 위와 같은 RB 트리에서 10 노드를 삭제하면 어떻게 될까?

우선, 10 노드는 자식 노드가 없으므로 삭제되는 색은 10 노드의 색인 black이다.

그래서 문제 발생 여부를 확인해보니, #5 속성을 위반하게 되었다.

 

다음과 같이 재조정한다.

1. 10 노드를 대체한 nil 노드에 extra black을 부여한다.
2. #2 속성에 따르면 nil 노드는 black으로 취급하므로, 해당 노드는 double black이 된다.
3. 이제 black height을 재측정하면 문제가 없음을 확인할 수 있다.

 

만약 30 노드를 삭제한다면 다음과 같이 재조정된다.

 

 

 

red-and-black 해소

이번에는 extra black을 회수하는 것을 어떻게 하는지 살펴보자.

앞서 언급했듯 red-and-black 해소는 해당 노드를 black으로 바꾸면 되는 매우 간단한 조정이다.

 

double black 해소

이제, double black 해소 방법을 케이스별로 살펴보자.

여기서는, 앞 포스팅에서도 다룬 5번 속성의 파생 특징이 중요한 역할을 한다. 

• RB 트리가 5번 속성을 만족하고, 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 뒤바꿔도 5번 속성은 여전히 만족한다.
• 즉, 부모 자식의 색상은 자유롭게 바꿔도 된다는 것!

case 1, 2, 3, 4를 역순으로 살펴볼 것이다.

그 이유는 case 4의 해결법이 case 2, 3에서 재활용되고, case 2, 3, 4의 해결법이 case 1에서 재활용되기 때문이다. 

 

case 4.  double black의 오른쪽 형제가 black, 그 형제의 오른쪽 자녀가 red일 때

 

이런 상황이다. 이를 해소하는 핵심 아이디어는 'red 색상을 A 노드의 부모 위치로 옮기고, extra black을 red 색상에 준 다음, 해당 red-and-black을 black으로 바꿔준다!' 이다. 

 

어떻게 해야 red 색상을 건너 건너~~ A의 부모 위치까지 옮길 수 있을까? 

1. 형제와 형제의 자식(D와 C, E)을 color flip 해준다. 
   • 이때, red일수도 black일수도 있는 왼쪽 자식(C)은 extra black을 하나 받은 것으로 처리한다.
2. 부모와 형제(B와 D)를 color flip 해준다.
3. 부모 기준으로 좌회전한다.
   • 좌회전 한 이후에도 #5 속성은 여전히 만족한다. 이 이유는 따로 증명이 필요한 부분.
4. double black과 (새로 생긴) 형제 노드의 extra black 두 개를 합쳐서 부모 노드에게 올려준다.
   • 그럼 부모 노드는 red-and-black이 된다.
5. 부모 노드를 black으로 바꿔주면 완성

(1) 형제, 형제의 오른쪽 자식을 color flip -> (2) 부모와 형제를 color flip -> (3) 좌회전

 

(4) extra black 두개를 모아 부모에게 보냄 (5) 결과

 

이렇게 하면 모든 문제가 해소되었다.

그리고 결과론적인 방법으로, 역으로 해당 결과가 나오게끔 간소화된 과정을 만들어보면 다음과 같다. 

 

1. 형제 노드는 부모 노드의 색을 물려받는다. 
2. 부모 & 형제의 오른쪽 자식 노드는 검은색으로 바꾼다.
3. 부모 노드를 기준으로 좌회전한다. 

 

(1) 초기 상태 (2) 삼촌 노드에 할아버지 색 물려주기&할아버지와 삼촌의 자식노드 black으로 바꾸기 (3) 좌회전 후 결과

 

 

 

case 3: double black의 형제가 black + 형제의 왼쪽 자녀는 red, 오른쪽 자녀는 black인 경우

이 경우 핵심 아이디어는 다음과 같다: "형제의 왼쪽 자녀가 갖고있는 red를 오른쪽 자녀 자리로 넘겨주면 case 4와 같은 상황이 된다. 그 이후엔 case 4의 해결방법을 그대로 적용한다."

 

그럼 어떻게 왼쪽에 있던 red를 오른쪽으로 넘겨줄까?

-> 형제와 형제의 왼쪽 자녀(D와 C)를 color flip 하고 우회전해주면 된다. 

 

1. 형제와 형제의 왼쪽 자녀를 color flip한다.
2. 형제 기준으로 우회전한다.
3. 이제 case 4와 동일한 상태이다. 

 

 

case 2: double black의 형제가 black + 형제의 양쪽 자녀가 black인 경우

case 4에서 형제의 extra black을 모아서 부모에게 전달한다는 아이디어를 가져온다.

 

1. 더블 블랙의 extra black과 형제의 black을 모아서 부모 노드에게 전달한다.
2. 그럼 부모는 red-and-black 또는 double black이 된다.
   1. 이로써 기존의 double black인 A는 해소가 됐다. 
3. 이제 extra black이 부모에게 옮겨갔다. 이 경우 3가지 case로 나뉜다. 
   1. 부모가 red-and-black 일 경우 -> black으로 바꿔서 해결
   2. 부모가 루트 노드일 경우 -> black으로 바꿔서 해결
   3. 부모가 더블 블랙이고 루트 노드가 아니라면 -> 부모 노드의 관점에서 다시 double black 해소 시작 (case 1, 2, 3, 4)

 

 

case 1: double black의 형제가 red인 경우

이 경우 더블 블랙의 형제를 black으로 만들어주면, case 2, 3, 4 중에 하나에 속하게 될 것이다. 

따라서 형제를 black으로 만들고 그 다음에 케이스에 따라 대응한다. 

 

1. 부모와 형제를 color flip 한다.
2. 부모 기준으로 좌회전한다.
3. 이제 case 2, 3, 4 중에 하나와 같은 상황이다.

 

 

 

 

 

---

삭제 연산 진행과정 총정리 (pseudo code에 가까운 ver)

실제 구현할 때는 추상적인 개념인 extra black을 실제로 구현하지는 않는다.

다만 extra black를 부여하고 회수하는 효과를 코드로 구현한다. 

 

1. BST와 동일하게 삭제연산을 진행한다.
2. 삭제되는 색을 파악한다.
   (굳이 삭제되는 색이라는 이상한 표현을 쓰는 이유는, 노드가 삭제되면서 색까지 품고 삭제되는 경우가 있고(branch의 최하단(혹은 최하단 +1 레벨)에 위치한 경우), 노드의 key값은 사라지지만 색과 부모 자식 관계를 그대로 물려받는 경우가 있기 떄문이다.)
   
   1. 자녀가 0 or 1개 = 해당 노드를 그대로 없애주고, 해당 노드의 색이 곧 삭제되는 색이 된다.
   2. 자녀가 2개 = 해당 노드 위치를 대체하는 successor가 해당 노드의 색을 물려받는다. 따라서 successor의 색이 곧 삭제되는 색이 된다.
3. 삭제되는 색이 red라면 문제 X.
4. 삭제되는 색이 black이라면 속성 #2, #4, #5 위반 여부를 검사한다.
   1. 속성 #2를 위반했다면 루트 노드를 black으로 바꿔준다.
   2. 속성 #4 위반 사례는 #5 위반의 부분 집합이다. 따라서 #5 위반을 해소하는 과정에서 함께 해소된다.
   3. 속성 #5 위반 사례(black height 불일치)의 해결 과정은 다음과 같다. (extra black을 준다는 추상적 개념을 과정에 녹인 ver)
      1. 삭제된 노드 위치를 대체한 노드 x가 red일 경우, black으로 바꾼다.
      2. 삭제된 노드 위치를 대체한 노드 x가 black일 경우, 형제와 형제의 자식 노드 색깔을 체크한다.
         • case 4. 형제 = black, 형제의 오른쪽 자식 = red
           1. 형제는 부모의 색을 물려받는다.
           2. 부모와 형제의 오른쪽 자식은 black으로 바꾼다.
           3. 부모 기준 좌회전한다.
         • case 3. 형제 = black, 형제의 오른쪽 자식 = black, 왼쪽 자식 = red
           1. 형제와 형제의 왼쪽 자식을 color flip
           2. 형제 기준으로 우회전한다.
           3. case 4와 동일
         • case 2. 형제 = black, 형제의 오른쪽 자식 = black, 왼쪽 자식 = black
           • 형제를 red로 바꾼다.
             • 이때 x는 double black에서 해소된다. (개념상 x의 extra black과 형제의 black을 extra black의 형태로 부모에게 올려줌 <- 그래도 black height은 유지되기 때문에 가능한 방법)
             • 형제의 자식 노드는 모두 black이므로 이 시점에서 x와 x의 형제는 모두 문제가 없는 상태가 된다.
           • 이때, 부모는 새롭게 extra black을 부여받은 노드가 된다. 따라서 부모의 상태에 따라 반복적인 재조정을 수행한다.
             • 부모가 원래 red였던 경우: 부모를 black으로 바꾼다.
             • 부모가 루트 노드인 경우: 부모를 그냥 black으로 지정하고 마무리한다. 
             • 부모가 원래 black이었으며, 루트 노드가 아닌 경우: 부모가 새로운 x(더블 블랙 노드)가 된다. 
         • case 1. 형제 = red
           • 부모와 형제를 color flip
           • 부모 기준으로 좌회전
           • case 2, 3, 4 중 하나와 동일한 상태가 된다. 

 

우리가 이해하기에는 case 4를 먼저 배우고 나머지에서 재활용된다는 식의 설명이 편하지만,

역으로 case 4는 모든 case에서 재활용되기 때문에 실제 코드에서는 case 1 -> 2, 3 -> 4 순으로 처리하는 것이 효율적이다.

때문에 case 1, 2, 3, 4가 코드 단에서 보면 맞는 순서이고, 우리는 이를 거꾸로 배우는 것이다.

 

---

Q. 삭제 연산을 반복하면 할 수록 black 노드의 비중이 높아지는데, 그래도 rb tree의 속성 유지에는 영향이 없나?

 

n개의 내부 노드를 가지는 rb 트리는 최대 2log(n+1)의 높이를 가진다.(CLRS p.312 에 증명이 있음)

-> 최소 높이는 모든 노드가 black인 경우 = log(n+1)

-> 최대 높이는 black과 red가 번갈아가면서 리프까지 도달하는 경우 (#4 조건) = 이 경우 높이는 최소 높이의 2배 = 2log(n+1)

---

레퍼런스

https://www.youtube.com/watch?v=6drLl777k-E