레드블랙트리 - 삭제

레드블랙트리 삭제

레드블랙트리의 삭제는 기본적으로 이진탐색트리의 삭제에 기반 한다.

이렇게 노드를 삭제하고 나면, 무너진 레드블랙트리의 규칙을 복원하는 것에 초점을 둔다.

첫째로 삭제된 노드가 RED 인 경우 어떠한 추가 작업도 필요하지 않다.

왜냐면 규칙이 무너지는 경우는 RED 노드가 연속적으로 부모 자식 관계인 경우인데

RED 가 삭제되는 걸로는 해당 규칙을 벗어나지 않기 때문이다.

하지만 검은색 노드를 삭제하는 경우가 문제가 된다.

이때는 상황에 따라서 문제를 해결해 주어야 한다.

Default 케이스

     Default 케이스는 삭제가 일어나면 무조건 실행되는 케이스이다.

     삭제된 노드가 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다.

삭제하려는 노드가 75 인 경우 그 자릴 대체할 노드는 70 이다.	자식이 1개 있는 경우기 때문에 75의 부모와 70을 연결해 준다.
연결한 노드를 검은색으로 칠함으로서 문제를 해결한다.

     이것으로 문제가 해결되면 좋겠으나, 그 자리를 대체하는 노드가 검은색이었다면 문제가 된다.

     이 경우, 원래 검은색 노드를 다시 검은색으로 칠하는 경우로, 이런 노드를 이중흑색노드 라고 부른다.

     이중 흑색노드를 해결하려면, 해당 케이스 별로 처리방식이 다르다.

     지금부터 알아 볼 경우는 이중흑색노드가 부모의 왼쪽자식일 경우를 기준으로 설명한다.

     따라서 이중흑색노드가 부모의 오른쪽 자식인 반대경우도 고려해야 함을 명심하자.

● 이중 흑색노드 처리

CASE Change - 이중흑색노드의 형제가 RED 인 경우.

형제를 검은색, 부모를 빨간색으로 칠한다. 부모노드를 기준으로 좌회전 한다.

삭제하려는 노드가 10 인 경우 그 자릴 대체할 노드는 NIL 이다. (NIL 역시 검은색 노드이다.)	10 노드가 삭제되면, 그 자리를 NIL 노드가  대체하게 되고, 이것을 검은색으로 칠한다는  것은 NIL 노드가 이중흑색노드가 되는 셈이다. 이때 이중흑색노드의 형제 150 이 RED 이다.
형제를 검은색, 부모를 빨간색으로 칠한다. 그리고 부모를 기준으로 좌회전을 수행한다. NIL 노드는 여전히 이중흑색 노드이며, 형제가 RED 가 아닌 BLACK 인 경우로 바뀌었다. 이제 다음에 나올 CASE 에 따라 처리를 하면 된다.

CASE A - 이중흑색노드의 형제가 BLACK 이고 형제의 양쪽 자식 모두 BLACK 인 경우

형제노드만 RED 로 만들고, 이중흑색노드의 검은색 1개를 부모에게 전달한다. 

삭제하려는 노드가 11 인 경우 그 자릴  대체할 노드는 NIL 이다.  (NIL 역시 검은색 노드이다.) 11 노드가 삭제되면, 그 자리를 NIL 노드가  대체하게 된다.	NIL 노드가 이중흑색노드가 되었고,  이중흑색노드의 형제 150 이 BLACK 이며  그 두 자식도 BLACK 이다.

형제만 RED 로 만들고, 이중흑색노드의 검은색을 부모에게 전달한다.   부모가 RED 였다면 검은색으로 칠하고 끝났을 테지만, 부모가 검은색인 경우라서 때문에 이중흑색노드가 되고 말았다.   따라서 부모가 이중흑색노드가 된 경우, 그 부모도 다시 CASE 상황을 거쳐서 밸런스를  계속 복구해 나가야 한다. 위 예제 그림에서는 100 노드의 형제가 검은색이이고  그 두자식이 다 검은색인 경우이므로, CASE 1 의 재탕이다. 그 형제인 1000 노드를  RED 로 만들고 부모에게 검은색을 전달한다.

이렇게 부모에게 검은색을 전달하면서, 그 위로 밸런스를 복구하다가 ROOT 에  도달하게 되면 작업이 끝나게 된다.

CASE B - 이중흑색노드의 형제가 BLACK 이고 형제의 왼쪽 자식이 RED, 

            오른쪽 자식이 BLACK 인 경우

형제노드를 RED 로, 형제노드의 왼쪽 자식을 BLACK 으로 칠한 후에 

형제노드를 기준으로 우회전 한다.

삭제하려는 노드가 60 이다.	이중흑색노드 NIL 의 형제의 왼쪽자식이 RED, 오른쪽 자식이 BLACK 이다.

형제노드인 78 을 RED 로 만들고, 형제노드의 왼쪽 자식을 BLACK 으로 만든 뒤에 형제노드를 기준으로 우회전 한다.

CASE C - 이중흑색노드의 형제가 BLACK 이고 형제의 오른쪽 자식이 RED 인 경우

 부모 노드의 색을 형제에게 넘긴다. 부모노드와 형제노드의 오른쪽 자식을 

검은색으로 칠한다. 부모노드 기준으로 좌회전 한다.

삭제하려는 노드가 77 이며, 삭제후 NIL 노드가 이중흑색 노드가 된다.	이중흑색노드 NIL 의 형제의 왼쪽자식이 RED, 오른쪽 자식이 BLACK 이다.
부모 100 노드의 색을 형제에게 넘긴다. 부모노드(100) 와 형제노드의 오른쪽 자식(175) 의  색을 검은색 으로 칠한다. 부모노드(100) 기준으로 좌회전을 한다.

- by Raimondo