Red-Black tree

레드블랙 트리(red-black tree)는 이진 검색 트리로서, 각 노드당 한 비트의 추가 기억 공간을 가진다.

이 비트는 RED 또는 BLACK의 색깔을 나타낸다.
루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써, 트리의 균형을 근사적으로 유지한다.

특성

다음 5개의 레드블랙 특성을 만족하는 이진 검색 트리를 레드블랙 트리라고 한다.

1. 모든 노드는 적색이거나 흑색이다.
2. 루트는 흑색이다.
3. 모든 리프(NIL)는 흑색이다.
4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

• 특성 2,4,5가 삽입/삭제 연산이 일어날 때 주로 위반되는 특성들.
• 특성 1은 당연해 보이지만, 이후 트리의 균형을 맞추는 과정(FIX-UP)에서 흑색의 개수를 조절할 때(즉, 특성 5 위반을 복구할 때) 색이 확정되지 않은 노드를 상정하고 진행하는 부분이 있다. 다시 말해, 특성 5의 위반을 특성 1의 위반으로 전환해 효율적으로 복구를 진행한다. 그 부분을 위해 존재.
• 특성 5에서 '모두'의 범위는, '그 노드에서 내릴 수 있는 경로들'이다. 트리 전체의 경로들이 아니다.
• 특성 3은 '루트의 부모의 색'이 흑색임을 보장해준다. 루트의 부모는 T.NIL 노드이기 때문이다.

센티널 노드 (sentinel node)

경계 노드.

• 코드 작성시 한계 조건을 다루기 편하게 해주는 더미(dummy) 노드 : T.nil
• 연산 시간의 상수인자를 줄일 수 있음.

센티널 노드를 활용하면 같은 트리도 (b)처럼 구현할 수 있다.

Sentinel Node vs NULL pointer

NULL pointer can —as in all binary tree data structures— encode the fact that there is no child node at this position in the (parent) node.

출처: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#req3

잘 생각해보면 굳이 센티널 노드를 써야할까 하는 의문이 들 수 있다. 그림 (a)에서 보이는 NIL을 실제 메모리가 할당되는 노드가 아닌 NULL로 바꿔서(key를 가진 노드 중 가장 끝 노드들의 자식 포인터들을 NULL을 가리키게 해서) 생각해도 트리의 구조에는 문제가 없다. 그렇다면 센티널 노드를 위한 메모리를 굳이 할당해서 (트리에서 딱 하나이긴 하지만.) 구현해야할 이유가 없을 것이다.

그럼에도 센티널 노드를 사용했을 때의 이점은 이름에서도 그대로 드러나듯 '경계값 처리의 유용함'에 있다. 리프노드(이 문장에서는 key를 가진 노드 중 가장 끝 노드들)를 삭제할 때를 생각해보자.

NULL 포인터를 사용한 구현에서는 리프노드를 삭제할 때 조건문을 줘서 따로 처리를 해주어야 한다. 삭제하고자 하는 노드가 u, 그 부모는 u.p, u의 자식은 v라고 한다면, u의 자리가 없어지기 때문에 u.p와 v를 이어서 트리가 끊기지 않게 해야할 것이다. 이를 구현하기 위해 (1) u.p 자식을 v로 설정하고, (2) v의 부모를 u.p로 설정하는 과정이 필요하다(포인터는 한쪽 방향만 볼 수 있기 때문.) u가 리프노드가 아니라면 u.p, v 둘다 존재하겠지만, 리프노드라면 v는 존재하지 않는다. (u의 자식 포인터는 NULL을 가리킨다). 그래서 리프노드는 위의 (2)과정을 수행할 수 없다. 따라서 조건문이 하나 필요할 것이다.

// using NULL pointer
void rbtree_transplant(rbtree *t, node_t *u, node_t *v){
  if (u->parent == null) {
    t->root = v;
  }
  else if (u == u->parent->left) {
    u->parent->left = v;
  } else {
    u->parent->right = v;
  }
  if (v != null) {				// v가 null이 아니라는 조건 == u가 리프노드가 아님.
  	v->parent = u->parent;
  }
}

하지만 센티널 노드를 사용한 구현에서는 리프노드 임을 체크하지 않아도 된다. 왜냐하면 리프노드(이 문장에서는 key를 가진 노드 중 가장 끝 노드들)의 자식은 T.nil이라는 '노드'로 '존재'하기 때문이다.

// using Sentinel Node
void rbtree_transplant(rbtree *t, node_t *u, node_t *v){
  if (u->parent == t->nil) {
    t->root = v;
  }
  else if (u == u->parent->left) {
    u->parent->left = v;
  } else {
    u->parent->right = v;
  }
  v->parent = u->parent;		// 조건문 없이 구현 가능.
}

아주 미미한 차이이긴 하나 전체 연산시간에서 상수인자를 줄일 수 있고, 코드가 더 명확해진다는 이점을 얻을 수 있다. 단, 이 역시 trade-off가 있다. 만약 원소의 개수가 적은 '트리(혹은 리스트)가 여러개 있는 경우', 센티널노드를 사용하기 위한 추가 메모리의 사용은 낭비가 될 수 있다.

RB-tree 말고도, 포인터를 사용해 링크를 구현하는 다른 자료구조에서 또한 같은 원리로 센티널 노드의 이점을 활용할 수 있다. 아래는 더블 링크드 리스트의 삭제 연산에 대한 코드이다. 마찬가지의 원리로 경계값 (리스트의 첫재값과 끝값)에 대한 조건문이 센티널 노드를 사용할 때는 필요없어진다.

// first and last are used to hold the address of first and last node.

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

출처 : https://stackoverflow.com/questions/5384358/how-does-a-sentinel-node-offer-benefits-over-null

회전

특성 복구 시 사용.
LEFT-ROTATE 와 RIGHT-ROTATE가 있는데 서로 대칭이다.

LEFT-ROTATE(T,x)
  y = x.right			// "y는 x의 오른쪽 자식을 말한다."

  x.right = y.left		// x의 직후 값, 그림에서는 β를 x가 오른쪽 자식으로 가져가는 구간.
  if y.left != T.nil   
      y.left.p = x    

  y.p = x.p				// y가 x자리에 오게되는 구간.
  if x.p == T.nil
      T.root = y
  else if x == x.p.left
      x.p.left = y
  else // x == x.p.right
      x.p.right = y	

  y.left = x			// x가 y의 왼쪽자식이 되는 구간.
  x.p = y

삽입

삽입되는 노드 Z에 대하여,
Z를 삽입하고(기본 이진트리의 삽입과정과 같다.) 적색으로 칠한다 (RB-INSERT).
이후에 발생할 수 있는 위반을 복구한다 (RB-INSERT-FIXUP).

RB-INSERT-FIXUP에 있는 반복문이 실행되면서, Z가 가리키는 노드는 위로 올라간다.

발생 가능한 위반은 아래의 두가지인데, 두가지를 한꺼번에 위반하지는 않는다.

• 특성 4 위반 : "노드가 적색이면 그 노드의 자식은 모두 흑색이다."
  Z가 적색으로 삽입된 상황에서, Z의 삽입위치 위의 부모가 적색이면 특성 4를 위반하게 될 것이다.
  
  
• 특성 2 위반 : "루트는 흑색이다."
  Z가 가리키는 노드는 항상 적색임을 상기하자.
  (RB-INSERT 시에도 적색으로 칠하고, RB-INSERT-FIXUP의 반복문 안에서도 이후 반복에서 Z가 가리키게될 노드를 적색으로 칠한다.)
  
  따라서, 맨 처음 삽입시에 Z가 루트위치에 왔거나 (빈 트리였을 때),
  RB-INSERT-FIXUP 내의 반복문 진행되면서 Z가 루트를 가리키게 될 때 위반될 것이다.

전체적인 구조는 RB-INSERT-FIXUP의 반복문 안에서 특성 4가 복구되고,
반복문을 빠져 나온 후 다음 라인에서 특성 2가 복구될 수 있다.

코드를 먼저보자.
RB-INSERT 는 이진트리의 삽입 과정과 거의 다르지 않다. 다만 리프노드의 자식을 T.nil로 설정해줘야하고, Z를 삽입 후 적색으로 칠해주어야 한다.

RB-INSERT(T,z)
  /*
  	일반 이진트리의 삽입 과정과 동일.
  */
                            // RB-INSERT의 차이점.
  z.left = T.nil			// 리프노드의 자식을 T.nil로 설정해줘야하고,
  z.right = T.nil			//
  z.color = RED				// Z를 삽입 후 적색으로 칠해주어야 한다.

  RB-INSERT-FIXUP(T,z)		// 삽입 후 위반된 특성을 복구해보자.

RB-INSERT-FIXUP(T,z)
  while z.p.color == RED
    if z.p == z.p.p.left
  		  y = z.p.p.right			// "y는 z의 삼촌"
  
  		  if y.color == RED			// 경우 1 : 삼촌이 적색. (부모 z.p도 이미 적색)
  	  		  z.p.color = BLACK
  	  		  y.color   = BLACK
  	  		  z.p.p.color = RED
  	  		  z = z.p.p			    // z를 조부모로 두고 while문 반복.
  
  		  else						// 경우 2,3 : 삼촌이 흑색.
              if z == z.p.right		// 경우 2 : 삼촌이 흑색이고, z는 부모의 오른쪽 자식.
                  z = z.p				// 경우 3가 되기 위해(=왼쪽자식이 되기위해) 회전하기전 미리 z포인터를 조정
                  LEFT-ROTATE(T,z)
  
              z.p.color = BLACK		// 경우 3 : 삼촌이 흑색이고 z는 부모의 왼쪽 자식.
              z.p.p.color = RED
              RIGHT-ROTATE(T,z.p.p)
  
    else
  	  /*
  	    위와 대칭. (z.p == z.p.p.right인 경우이므로.)
  	  */
  
  T.root.color = BLACK		// 반복문 빠져나와서(혹은 첨부터 실행이 안되서) 특성 2 위반 있을 경우에 대비.

반복문 안에 들어있는 경우 1,2,3 은 특성 4 위반을 복구하기 위한 케이스다.

경우 1 : 삼촌이 적색인 경우.
경우 2 : 삼촌이 흑색이고, z가 부모의 오른쪽 자식일 경우.
경우 3 : 삼촌이 흑색이고, z가 부모의 왼쪽 자식일 경우.
(여기서의 경우 2,3은 z의 부모가 왼쪽 자식일 경우임.)

경우 1은 반복문 실행 후 다시 경우 1이 되거나, 경우 2,3으로 바뀐다.
경우 2,3은 반복문 실행후 반복이 종료된다.

• 경우 1 : 삼촌이 적색인 경우
  
  부모 z.p도 이미 적색이므로 z의 윗단계 (부모, 삼촌)은 전부 적색이다.
  그래서 위 그림처럼 z의 윗단계를 전부 흑색으로 만들고, 조부모를 적색으로 만들어
  (반복문 실행 전 조부모(z.p.p)는 무조건 흑색이다. 왜냐하면 부모(z.p)가 적색이고, 삽입하기 전 트리는 위반이 없었기 때문에, z와 z.p사이의 위반만 존재할 수 있기 때문이다.)
  트리의 특성을 유지시킨 후, z를 조부모로 다시 설정하고 반복문의 처음으로 돌아간다.

• 경우 2,3 : 삼촌이 흑색인 경우
  
  (위의 그림에서 y가 삼촌이고 흑색이다.)
  
  먼저 경우 3을 먼저 보자.
  부모(B)를 흑색으로 만들고, 조부모(C)를 적색으로 만든 후, RIGHT-ROTATE하면 위반이 사라진다.
  경우 2는 A-B연결관계를 LEFT-ROTATE해서 경우 3의 모양과 같게 만들고 이후에는 같은 방법으로 위반을 없애면 된다.

삭제

먼저 기본 이진트리의 삭제는 두가지 종류가 있다. 삭제하고자 하는 노드를 Z라고 하자.

1. Z가 하나 '이하'의 자식을 가지고 있을 경우, 그 자식노드가 Z의 자리를 대신하면 된다.
   아래는 그 하나의 자식노드가 왼쪽 오른쪽이냐의 차이일 뿐.
   
2. Z가 두개의 자식을 가질 경우, Z의 직후원소 Y를 찾고 그 노드가 Z의 자리를 대신하게 하면 된다. 다만 Z의 '직후원소'란, 트리 전체의 원소의 key순서에서의 바로 다음 원소를 의미한다.
   그래서 아래와 같은 두가지 경우로 나뉠 수 있다.
   (c) : 직후원소 Y가 바로 밑 자식인 경우. - 한 번의 이식(transplant)이 필요
   (d) : 직후원소 Y가 바로 밑 자식이 아닌경우. - 두 번의 이식이 필요
   
   RB-TRANSPLANT() 는 말그대로 삭제된 노드 위치에 대체할 노드를 '옮겨심는' 함수이다.

레드블랙 트리의 삭제과정 또한 기본 이진트리의 삭제과정과 거의 유사하다.
단, 삭제하는 과정에서 노드들의 위치가 바뀌고, 그에 따른 전체적인 색 배열 또한 바뀔 수 있다.
이 과정에서 위반이 생길 수 있는데, 이러한 상황에 대비해 삭제한 노드의 원래 위치를 채우는 노드들을 추적하면서 위반을 탐지하고 복구한다.

이를 위해 Z가 삭제된 자리를 채우는 노드를 Y로 설정한다.
그리고 Y가 이동하면서 원래 Y의 빈자리를 채우는 노드 또한 존재할 것이다. 그 노드를 X로 설정한다.
위의 2번의 (c),(d)에서 보이듯이, Z의 원래 위치에 Y가 들어가고, Y의 원래 위치에 X가 들어간다.
이 경우를 Y는 이동한 노드를 가리킴이라고 표현할 것이다.

다만, 1번의 경우에는 뒤에서 등장할 반복문에서의 변수의 범용성을 위해, Y가 바로 Z의 자리를 채운 후(덮어씌운다고 생각하자) 바로 삭제된다. 그 후 그 자리를 X가 채운다.
이 경우를 Y는 삭제된 노드를 가리킴이라고 표현할 것이다.

앞서 언급 했듯, 이러한 추적의 의미는 바뀐 색 배열이 유발하는 위반을 바로잡기 위함이다.
어떠한 위반이 가능한지를 알아보기 전에 코드를 먼저 살펴보자.

RB-DELETE(T,z)

  // 1. "Y가 삭제된 노드를 가리키는 경우". 즉, 삭제되는 노드 Z의 자식이 하나인 경우.
  y = z
  y-original-color = y.color		// y의 원래 색을 저장해둔다.
  if z.left == T.nil				// 그 하나의 자식이 오른쪽에 있는 경우를 의미.
	  x = z.right					// 그 자식을 x라고 두고
	  RB-TRANSPLANT(T,z,z.right)	// z의 원래자리(1행에서 y가 된.)를 대체함.

  elseif z.right == T.nil			// 그 하나의 자식이 왼쪽에 있는 경우를 의미.
	  x = z.left
	  RB-TRANSPLANT(T,z,z.left)

  // 2. "Y가 이동한 노드를 가리키는 경우". 즉, 삭제되는 노드 Z의 자식이 두개인 경우.
  else
	  y = TREE-MINIMUM(z.right)		// 'y는 z의 직후원소'. z의 우측 서브트리의 최소값을 찾으므로써 얻는다.
	  y-original-color = y.color
	  x = y.right						// 'x는 y의 자식'. 서브트리의 최소값을 가진 노드이기 때문에 왼쪽 자식이 없다. 그래서 x는 바로 오른쪽 자식으로 지정한다.
    
	  // y가 z의 바로 밑 자식일 때. 위의 (c)의 경우.
	  if y.p == z						
		  x.p = y						// x가 T.nil일 때를 대비해 x.p를 굳이 y로 명시해 준다. 아래에서 자세히 설명.

	  // y가 z의 바로 밑 자식이 아닐 경우. 위의 (d)의 경우.  	
	  else							
		  // (d)의 중간단계를 만드는 과정이다.
		  RB-TRANSPLANT(T,y,y.right) 	// x(y.right)을 y의 자리로 옮겨 심어준다 즉,
									// x.p = r 의 결과를 낸다.
		  y.right = z.right			// r(z.right)을 y의 오른쪽 자식으로 만든다.
		  y.right.p = y				// r의 부모를 y로 만든다.

	  RB-TRANSPLANT(T,z,y)			// y를 z의 원래 자리에 옮겨 심는다.
									// (d의 경우엔)바로 위에서 만든 서브트리의 루트 y를 z의 자리에 옮겨심는 라인.
									// (c의 경우엔)z의 바로 밑 자식 y를 z의 자리에 옮겨심는 라인.
	  y.left = z.left				// 원래 z의 왼쪽 자식들 이어받기.
	  y.left.p = y
	  y.color = z.color				// y의 색을 원래 z가 자기자리에서 갖고 있던 색으로 강제한다.
									// 이유는, z가 자식이 하나일때는 상관이 없었는데, 두개 일때는 y말고도 왼쪽 자식이 있었으니 그들과의 색 배열을 어긋나지 않게 하기 위함이다.
									// 하지만 y자신이 루트로 있던 서브트리에서는 y의 색깔이 z의 원래색으로 강제당했으니(바뀌었으니) 색 배열이 어긋날 수 있다.
									// 이 것의 의도는 결국, 어긋남의 범위를 지금 추적하는 값들 안에서 일어나게 제한한 것이라고 볼 수 있다.
  if y-original-color == BLACK
	  RB-DELETE-FIXUP(T,x)			// 위반을 고쳐보자..

...
x = y.right

// y가 z의 바로 밑 자식일 때. 위의 (c)의 경우.
	  if y.p == z						
		  x.p = y
...

여기서의 x.p = y의 의미는 x가 T.nil일 때 그 T.nil노드의 부모를 갱신해주기 위함이다. 원래 x의 부모를 y로 설정해줄 필요가 없다. 해당 코드의 바로 윗 줄에서 x = y.right가 실행되기 때문에 x가 y의 자식임이 명백하기 때문이다. 새로 insert된 값도 아닌, 원래 트리구조에 있던 자식이므로 그 노드 안의 부모 정보도 정확히 들어있다.
하지만 y.right 이 T.nil 이었다면, x에게 부모 정보는 존재하지 않는다. 정확히는 그 부모 정보(T.nil.p)가 y가 아닐 수 있다. T.nil는 전체 트리에서 딱 하나인 노드이기 때문에, 여러 삽입과 삭제 과정에서 안의 변수가 계속해서 바뀐다.(color는 BLACK으로 고정.)

• Its color attribute is BLACK, and its other attributes—p, left, right, and key—can take on arbitrary values.
• The values of the attributes p, left, right, and key of the sentinel are immaterial, although we may set them during the course of a procedure for our convenience.

이 값들이 어떤 의미나 용도를 가지진 않지만, 적어도 위의 삭제 함수에서는 반드시 T.nil.p 의 정보를 현재 함수 실행 과정에 맞게 설정해줘야 한다. 왜냐하면 x는 T.nil 노드이기 이전에 현재 삭제 연산에서 y의 자식으로서, 이후 RB-DELETE-FIXUP(T,x)의 인자로 전달되고, 이 함수 내에서 x는 자신의 부모 정보를 통해 자신의 형제(w)의 정보를 얻을 수 있어야 하기 때문이다.
만약 이러한 필요성이 없다면, 굳이 x.p = y를 통해 따로 명시할 필요가 없다. 실제로 일반 이진 탐색 트리의 삭제 과정에서는 y.p == z에 대한 조건이 없고 y.p != z일때만 RB-TRANSPLANT(T,y,y.right); y.right = z.right; y.right.p = y; 을 실행할 뿐이다.

뭐가 많지만 정말 크게 봤을 때, Z를 대체하는 Y의 색이 적색이냐 흑색이냐에 따라 위반 발생 여부를 살펴볼 수 있겠다.

1. Y가 적색일 때 ➡️ 위반이 발생하지 않는다.
   Y가 적색이므로 그의 자식인 X의 색은 흑색일 수 밖에 없음을 기억하고 있자.

   • 흑색 높이는 모두 그대로 유지된다.
     1) Y는 삭제된 노드를 가리킴의 경우 :
     - 적색인 Y(=Z)의 자리에 흑색인 X가 들어갈테니 경로상의 흑색의 개수는 변하지 않는다.
     
     2) Y는 이동한 노드를 가리킴의 경우 :
     - 위의 코드에서 보듯이 Z의 색을 '적색인 Y'에게 강제하게 되므로 흑색의 개수가 줄어들지 않는다.

   • 적색 노드가 인접하지 않는다.
     1) Y는 삭제된 노드를 가리킴의 경우 :
     - 적색인 Y(=Z)의 자리에 흑색인 X가 들어갈테니 적색 노드가 인접할 경우가 없다.
     
     2) Y는 이동한 노드를 가리킴의 경우 :
     - 위의 코드에서 보듯이 Z의 색을 Y가 그대로 물려받기 때문에 적색노드가 인접할(색배열이 어긋날) 경우가 없다. Y가 Z의 바로 밑 자식이 아닌 경우에 X가 Y의 자리를 차지하게 될 때 또한, Y가 적색임으로인해 X(Y의 자식)이 흑색이므로 적색노드가 인접할 경우가 없다.

   • Y가 적색이면 루트가 될 수 없으므로, 루트는 흑색으로 유지된다.
     1) Y는 삭제된 노드를 가리킴의 경우 :
     - 이 문장은 당연하다. Y는 바로 Z를 덮어쓰게 되는데 그러면 Y는 흑색이기 때문이다.
     
     2) Y는 이동한 노드를 가리킴의 경우 :
     - 이동 후에 Y는 Z의 색을 강제당하므로, 역시 상관이 없다.

2. Y가 흑색일 때 ➡️ 세 가지 위반 발생 가능.
   Y가 흑색이므로 X가 적색일 수 있다. 이 점을 기억하고 있자.

   ⚠️ 특성 2 : "루트는 흑색이다."

   • Y는 삭제된 노드를 가리킴의 경우에, Y가 루트고, Y의 적색 자식(X)이 새로운 루트가 된다면 루트가 적색이 된다. 'Y는 이동한 노드를 가리킴'의 경우가 아니기 때문에 Z(원래 루트였던)의 색이 강제되지도 않는다.

   ⚠️ 특성 4 : "노드가 적색이면 그 노드의 자식은 모두 흑색이다."

   • Y는 이동한 노드를 가리킴의 경우에, 이동 후에 X와 X.p( r )가 둘다 적색이면, 적색 노드의 자식이 적색이 된다. 원래 이동 전 흑색 Y가 r과 X 사이에 있었기 때문에 r과 X둘다 적색인 경우가 가능하다.

   ⚠️ 특성 5: "각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다."

   • Y는 이동한 노드를 가리킴, Y는 삭제된 노드를 가리킴 의 두가지 경우 모두에 대해, 흑색인 Y가 이동 또는 삭제됨으로써 Y를 원래 포함하고 있던 경로에서는 흑색 노드가 하나 줄게 된다. 왜냐하면 말그대로 원래의 Y가 그 자리에서 지키고 있던 색이 하나 없어지는 것이기 때문이다. 따라서 원래 Y의 조상(Z의 조상 or (Z or r))에 대해 특성 5가 위반된다.
     
     

   이 세 가지 위반을 RB-DELETE-FIXUP에서 해결 할 수 있다.
   위 함수의 반복문에는, 특성 1 위반을 해결하는 과정이 주로 담겨있다. 특성 5 위반을 어떠한 가정을 통해 아주 간단히 해결하면 특성 1 위반이 다시 발생하는데, 이런 식으로 문제를 전환해 복구를 용이하게 한다. 복구하는 과정에서 나머지 특성 2와 4 에 대한 위반이 함께 해결된다.

   어떤 가정을 한다는 것일까?
   바로 위에서 설명한 특성 5 위반에 대해 의문점이 한 가지 들 수 있을 것이다.

   '그러면 Y의 자리를 채우는 X를 흑색으로 바꿔주면 그만 아닌가?'

위 그림에서 보면 Z=Y = 75 이고, X = 70이다. X를 흑색으로 바꿔주니 실제로 위반이 복구되었다.
하지만 이렇게 해결 되지 않는 경우가 있다.

이중 흑색 노드 (Double Black Node)

위의 그림에서 Z=Y = B 이고, X = C 이다. 삭제된 자리에 X(C)가 들어가서 흑색이 되었지만, 특성 5 위반이 복구되지 않았다. 루트에서 C가 포함된 경로의 흑색의 개수는 2개이고, 나머지 경로들의 흑색 개수는 3개이기 때문이다. 즉, X가 있던 곳 조차 흑색이었으면 단순히 X를 기존 Y자리에 채워놓고 흑색으로 칠하는 것만으로는 복구가 불가능하다.

그래서 문제를 치환하기위해, 이중 흑색 노드라는 개념을 도입해 특성 5 위반을 무마해버린다.
잘 생각해보면, X가 무슨 색이었든 일단 흑색으로 칠하면 (흑색을 하나 더 주면) 원래 경로상의 흑색의 개수가 변하지 않을 수 있다.

1. 원래 X가 적색이었다면, 바로 전 전 그림처럼 단순히 X를 흑색으로 칠해주는 것으로 모든 위반이 복구된다.
2. 원래 X가 흑색이었다면, 그 흑색에 새로 칠해진 흑색이 더해져 흑색의 개수가 2개로 계산이 된다.(이중 흑색 노드가 된 것이다.) 그래서 특성 5 위반은 복구된다. -> 하지만 특성 1 위반이 발생한다.

결국 RB-DELETE-FIXUP의 반복문을 통해 다시 이 특성 1 위반을 복구하면 된다.
다시 말하면, 원래 흑색이었던 X가 받은 '여분의 흑색'을 반복문을 통해 없애면 된다.
코드를 보자..

  RB-DELETE-FIXUP(T,x)
    while x != T.root and x.color == BLACK
  		if x == x.p.left		
  			w = x.p.right				// 'w는 x의 형제.'
  
  			// 경우 1. 형제 w가 적색인 경우.
  			if w.color = RED
  				w.color = BLACK
  				x.p.color = RED
  				LEFT-ROTATE(T,x.p)
  				w = x.p.right
  
  			// 경우 2. 형제 w가 흑색. w 자식들 둘다 흑색인 경우.
  			if w.left.color == BLACK and w.right.colot == BLACK
  				w.color = RED
  				x = x.p
  
  			else
  				// 경우 3. 형제 w가 흑색. w의 왼쪽자식은 적색, 오른쪽 자식은 흑색인 경우.
  				if w.right.color == BLACK
  					w.left.color = BLACK
  					w.color = RED
  					RIGHT-ROTATE(T,w)
  					w = x.p.right
  
  				// 경우 4. 형제 w가 흑색. w의 오른쪽 자식은 적색인 경우.
  				w.color = x.p.color
  				x.p.color = BLACK
  				w.right.color = BLACK
  				LEFT-ROTATE(T,x.p)
  				x = T.root
  		else
  		  /*
  			위와 대칭. (x == x.p.right인 경우이므로.)
  		  */
    x.color = BLACK  	// 반복문 종료되면(x가 루트 또는 적색노드를 가리킬 때) x를 흑색으로 칠한다.
  						// 루트를 가리킬 때는 이미 이중 흑색 노드의 여분의 흑색이 다른 노드에게 나눠진 상태이고,
  						// 적색노드를 가리킬 때는 여분의 흑색을 하나 가져온 것이므로, 지금 가리키고 있는 적색노드에 칠해주면 끝이다.
  
  

위 반복문의 탈출 조건은 X가 적색인 노드를 가리키게 되거나, X가 루트를 가리키게 되는 경우이다. 둘다 '여분의 흑색'을 그 노드에 칠함으로써 쉽게 처리할 수 있게되는 경우이다.
반면에 반복문이 실행되는 조건은 X가 흑색 노드를 가리킬 때, 즉 이중 흑색 노드일 때이다. 이는 4개의 경우로 나뉠 수 있다.

w를 x의 형제(sibling)라고 하자.
크게 w가 적색일 때(경우 1), w가 흑색일 때(경우 2,3,4)가 있다.

1. w가 적색인 경우.
   
   sibling(D)을 흑색으로, parent(B)를 적색으로 바꾸고, parent(B)를 기준으로 LEFT-ROTATE 한다.
   그러면 x의 new sibling(C)는 흑색이 되고, 경우 2,3,4 중 하나로 넘어갈 수 있다.
   이중 흑색 노드는 아직 남아있는 상태이다.

2. w가 흑색이고, w의 자식들이 둘다 흑색일 경우.
   
   c의 의미는 적색, 흑색 중의 하나라는 의미이다. x와 sibling 둘다 흑색인 상황인데, 각각에서 흑색 하나씩을 빼와서 (x에선 여분의 흑색, sibling은 자기가 가진 흑색) parent(B)에 전달한다. 이렇게 하면 양쪽 경로의 흑색 개수는 변하지 않으면서, 여분의 흑색을 B에게 넘길 수 있다.
   이후에 parent(B)를 새로운 x로 삼고 반복문을 다시 진행하는데, parent(B)의 원래 색상이 적색이었다면 반복문이 실행되지 않을 것이고, 흑색이었다면 이중 흑색 노드이기 때문에 (여분의 흑색을 받았으므로) 반복문이 다시 실행되어 경우 1,2,3,4 중 의 하나로 처리 될 것이다.

3. w가 흑색이고, w의 왼쪽 자식은 적색, w의 오른쪽 자식은 흑색인 경우.
   
   경우 3은 경우 4로 넘어가기 위한 준비단계이다. 경우 4에서는 반복문을 종료할 수 있다.
   sibling(D)은 적색으로, sibling의 left-child(C)는 흑색으로 색을 바꾸고, sibling(D)에 대해 RIGHT-ROTATE 을 할 수 있다. 이 과정에서 위반되는 특성은 없다. 이후에 c를 new sibling으로 설정하면, w가 흑색이고 오른쪽 자식이 적색인 경우 4로 넘어갈 수 있다.

4. w가 흑색이고, w의 오른쪽 자식은 적색.
   
   parent의 색을 sibling에 칠한다. 그리고 parent와 sibling의 right-child를 흑색으로 칠한다. 이후에 parent를 기준으로 LEFT-ROTATE(T,x.p)한다. 그 결과 오른쪽 그림에서 보이듯이 x의 이중 흑색이 A와 B에 분산되어 흑색의 개수가 유지되면서도 특성 1 위반이 복구되는 양상을 띠게된다. 그리고 위의 색칠과 회전의 결과에서 특성 4가 위반되지도 않는다. 이제 특성의 위반이 모두 복구 되었으므로, x가 루트를 가리키게해 반복문이 더이상 실행되지 않게 한다.

반복문은 경우 2와 4의 경우에서만 종료될 수 있다.

참고자료

CLRS (https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf)
https://m.blog.naver.com/PostView.naverisHttpsRedirect=true&blogId=cestlavie_01&logNo=220914445383
https://www.youtube.com/watch?v=nMExd4DthdA