Red Black Tree Removal

균형을 이루기 위한 red black tree의 특징

(1) 노드는 레드 혹은 블랙 색상 중 하나를 갖는다.

(2) 루트 노드는 블랙이다.

(3) 모든 리프 노드(또는 NIL 노드)들은 블랙이다.

(4) 레드 노드의 자식 노드들은 모두 블랙이다. (레드 노드는 연달아 나타날 수 없고, 블랙 노드만 레드 노드의 부모가 될 수 있다.)

(5) 각 노드로부터 해당 노드가 속한 하위 리프 노드까지의 단순 경로 상에는 블랙 노드 개수가 동일하다. (Black Height)

 

삭제(Removal)

- 이진 탐색 트리에서 두 개의 자식 노드를 가진 노드를 지울 때, 우리는 노드의 왼쪽 서브트리에서 최댓값을 찾거나, 오른쪽 서브트리에서 최솟값을 찾아 해당 값을 지우고자 하는 노드로 옮긴다. 이 때, 최댓값 또는 최솟값에 해당하는 노드는 반드시 한 개 이하의 자식 노드만 가질 수 있다. (최댓값, 최솟값이라는 타이틀 자체가 2개 이상의 자식 노드를 가진 노드에게 주어질 수 없기 때문이다.) 최댓값 또는 최솟값에 해당하는 노드를 옮기는 작업은 레드-블랙 트리의 속성을 위반하지 않는다. 문제가 되는 부분은 최댓값 또는 최솟값에 해당하는 노드가 옮기는 작업으로 인해 삭제되었을 때 주변 노드가 속성을 위반하는 지의 여부이다. 따라서 우리는 삭제에 있어서 최대 한 개의 자식을 가지고 있는 노드를 삭제하는 문제로 치환할 수 있다. 해당 문제에 대한 해법은 두 개의 자식을 가진 노드를 지우는 문제에도 적용할 수 있기 때문이다.

 

1번 규칙은 어떠한 노드를 delete한다고 해도 항상 참이다

간단한 상황

case 1 지울 노드가 red node일 때

(이 상황은 타겟이 두 개의 leaf 자식을 갖고 있을 때에만 발생한다. 왜냐하면 만약 M이 한 쪽에는 검은 non-leaf 자식 노드를 갖고 있고, 다른 쪽에 검은 leaf 자식 노드를 갖고 있다면, 양쪽의 검은 노드 개수가 달라지게 되어 특성 5를 위반하게 되기 때문이다.)

 - red node를 지울경우 2,3,4,5는 항상 참이다 -> Red nood는 root, leaf node가 아니기 때문에 2,3번은 항상 참

 - red node의 child는 항상 black node이기 때문에 4번도 참이 되며

 - red node를 지운다고 balck의 개수가 바뀌지 않기 때문에 5번도 참이된다.

 - 그러므로 red node를 지웠을 때는 어떠한 추가 처리가 필요하지 않다는것을 알게 된다.

 

case 2 지울 노드가 black node이고 치환되는 노드가 레드인경우

 - 일단 black node를 지우면 바로 5번 특성이 깨지게 된다 -> 다른 경로랑 black의 개수가 달라지기 때문에

 - 5번 특성을 지킬 방법은 삭제한 노드를 black노드로 대체하는 방법이 있다.

 

복잡한 경우 

6가지 case

case1. 치환된 노드가 블랙이며 root node의 자리에 온 경우 (전체적으로 black의 개수가 1개 줄어들었고, 새로운 노드는 검은색이므로 모든 특성이 보존된다.)

case2. 치환된 노드의 sibling이 red인 경우(이때 parent는 무조건 black일 수 밖에 없다.)

case3. 부모의 색상이 black인경우(부모의 반대편 서브 트리의 블랙의 개수가 1개 더 많아지기때문에 recursion을 이용하여 전체적으로 1개씩 빼줘야 한다. delete_case1부터 다시 진행)

case4. 부모의 색상이 red인경우

case5. 치환된 노드의 sibling이 블랙이고 left child node의 color가 red인 경우

case6. 치환된 노드의 sibling이 블랙이고 right child node의 color가 red인 경우