레드블랙트리 - 삭제

ㅇ레드블랙 트리 삭제

레드블랙트리의 삭제는 기본적으로 이진탐색트리의 삭제방식을 사용한다. 이후에 삭제하고 나면, 무너진 레드블랙트리의 규칙을 복원하는 것에 초점을 둔다. 첫째로 삭제된 노드가 RED 인 경우  작업이 필요하지 않다.  왜냐하면 규칙이 무너지는 경우는 RED 노드가 연속적으로 부모 자식 관계인 경우인데 RED가 삭제되는 걸로는 해당 규칙을 벗어나지 않기 때문이다. 하지만 검은색 노드를 삭제하는 경우가 문제가 된다. 

ㅇ이진 탐색트리의 삭제

이진 탐색트리의 삭제작업은 우선 삭제할 노드를 탐색하는 과정이 끝나면, 세 가지 경우로 나뉜다.

1.  삭제할 노드가 단말노드인 경우

삭제할 노드가 단말노드인 경우에는 그 부모노드가 해당 노드로의 연결을 끊고 리프노드를 연결해 준다.

2.  삭제할 노드가 자식노드를 한 개 가진 경우(왼쪽, 또는 오른쪽)

자식이 1개 있는 경우, 삭제할 노드가 부모의 왼쪽 자식인지 오른쪽 자식인지에 따라서 그 자리에 자기의 자식노드를 연결해 주면 해결됩니다.

3. 삭제할 노드가 2개의 자식을 가진 경우

자식이 2개인 노드를 삭제하려고 할 경우, 그 자리에는 누가 오는가? 노드의 값의 크기 순서를 해치지 않기 위해서, 중위 순회의 결과가 어긋나지 않는 값이 와야 할 것입니다. 즉 중위 후속자(In-Order Successor)  또는 중위 선행자(In-Order Predecessor을 찾아야 한다. ->  ++ 과  -- 연산자로 찾기 가능하다. 

따라서 자식이 2개인 노드를 삭제할 경우 중위 후속자가 오는 경우 삭제한 자리에 중위 후속자가 오는데  이러한 중위 후속자의 특징은, 자식이 없거나 1개라는 특징을 가진다. 중위 순회의 특성상 중위 후속자의 자식은 2개가 될 수 없다. 그 이유는 중위 후속자는 해당 노드의 오른쪽 자식으로 가서, 왼쪽 자식이 없을 때까지 도달했을 때가 바로 중위 후속자이기 때문이다. 

ㅇ 검은 노드 삭제한 경우

Default 케이스

Default 케이스는 삭제가 일어나면 무조건 실행되는 케이스이다. 삭제된 노드가 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다. 

위의 경우로 예를 들면 10을 삭제하면 다음 중위 후속자는 11이다. 10값에 11을 복사하고 그 자리를 검은색으로 칠해준다. 이것으로  문제가 해결되면 좋겠으나, 그 자리를 대체하는 노드가 검은색이었다면 문제가 된다. 이 경우, 원래 검은색 노드를 다시 검은색으로 칠하는 경우로, 이런 노드를 이중흑색노드라고 부른다. 이중 흑색노드를 해결하려면, 해당 케이스 별로 처리방식이 다르다. 지금부터 알아 볼 경우는 이중흑색노드가 부모의 왼쪽자식일 경우를 기준으로 설명한다.

따라서 이중흑생노드가 부모의 오른쪽 자식인 반대경우도 고려해야한다

ㅇ 이중 흑색노드 처리

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

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

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

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

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

형제노드를 RED로, 형제노드의 왼쪽 자식을 BLACK으로 칠한 후에 형제노드를 기준으로 우회전 한다.

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

부모 노드의 색을 형제에게 넘긴다. 부모노드와 형제노드의 오른쪽 자식을 검은색으로 칠한다. 부모노드 기준으로 자회전한다.