Red-Black Tree2

저번 포스팅에 이어 레드 블랙 트리가 노드의 추가, 삭제 시 규칙을 준수하도록 하여 트리가 균형을 유지하는 과정과 소스코드를 한번 공부해봤습니다.






<노드의 삽입>
레드 블랙 트리에 노드를 삽입하기 위해서 먼저 이진탐색트리와 같이 노드의 데이터 값을 기준으로 삽입할 위치를 이진탐색으로 찾아냅니다.






여기서 노드의 삽입으로 무너졌을지도 모를 레드-블랙 트리의 규칙을 살펴보겠습니다.






※ 레드-블랙 트리의 규칙
1. 모든 노드는 Red or Black
2. 루트 노드는 검은색
3. 잎 노드는 검은색
4. 빨간 노드의 자식 노드는 모두 검은색 but 검은색 노드의 자식이 빨간색일 필요는 없음
5. 루트 노드에서 모든 잎 노드 사이에 있는 경로의 검은색 노드 수는 모두 동일






먼저 새로운 노드를 추가할 때 무조건 추가되는 노드는 빨간색으로 가정하겠습니다.






이렇게 가정하는 이유는 일단 5번 규칙을 만족시키기 위해서 입니다.






무조건 추가되는 노드가 빨간색이라면 아무리 빨간색 노드가 많이 추가되어도 루트에서 잎 노드로 가는 경로의 검정 노드의 수는 항상 같기 때문입니다.






그리고 새로운 노드를 Red-Black 트리에 추가한다고 1번 규칙이 무너지지도 않습니다.






왜냐하면 새로운 노드는 항상 빨간색이고 원래 트리에 있는 모든 노드는 빨간색 or 검은색이므로 1번 규칙 준수하기 때문입니다.






그리고 마지막으로 3번 규칙을 만족시켜주기 위해서 제가 만들 트리에는 잎 노드의 자식으로 검정색 더미 노드를 만들 것입니다.


즉 예를 들면









이와 같은 형식으로 레드 블랙 트리가 구성 되는데 여기서 NIL은 3번 규칙을 만족 시키기 위해서 임의적으로 추가한 아무런 데이터도 가지지 않는 더미노드입니다.


여기서 이론적으로는 위의 그림과 같지만 메모리의 낭비를 막기 위해서





이와 같은 방식으로 구성하였습니다. 어차피 NIL은 아무런 의미없는 3번 규칙만 만족시켜주기 위한 더미노드이기 때문에 이렇게 구성한다고 문제될 건 아무것도 없습니다.


여기서 새로운 노드를 추가할 경우에는 빨간색 노드가 특정 잎 노드의 자식노드로 추가되게 됩니다.


그리고 새롭게 추가된 노드의 양쪽 자식으로 NIL 더미 노드에 연결시켜 주면 새로운 노드가 추가되어도 3번 잎노드는 검은색이라는 규칙을 어기지 않게 됩니다.


즉 새로운 빨간색 노드를 추가했을 경우 1번 3번 5번 규칙은 어기지 않게 되지만 2번 4번 규칙을 어길수 있습니다.


먼저 2번 규칙을 어길경우는 새로 추가되는 노드가 트리의 첫번째, 즉 루트노드일 경우입니다.


이 경우는 단순히 그 노드를 검은색으로 바꿔주기만 하면 됩니다.


그리고 이 경우 말고도 나중에 2번 규칙이 어겨지는 경우가 있는데 그건 그 때 다시 설명 드리겠습니다.


또 4번 규칙을 어기는 경우는 리프노드(더미 리프노드가 아닌 실제 리프노드)가 빨간색인 곳의 자식노드로 새로운 노드가 추가되는 경우입니다.


여기서부터 3가지 경우에 따라서 재구성 되는데 이 때 사용하는 연산이 제가 처음 레드 블랙 트리를 포스팅 했던 곳에서 올렸던 회전 연산입니다.


(새로 추가한 노드의 부모노드가 할아버지 노드의 왼쪽 자식일 경우)


밑에서 설명할 때 레드-블랙 트리의 일부분만 가져와서 설명했습니다.


즉 할아버지 노드의 위로 부모노드 1개까지 나타냈는데 그 위로도 많은 부모노드와 형제노드가 있을 수 있다고 생각하시면 됩니다.


1) 삼촌 노드가 빨간색일 경우

이러한 경우에는 부모 노드와 삼촌 노드를 검은색으로 바꾸고 할아버지 노드를 빨간색으로 바꿉니다.

그러면 이렇게 변하게 되는데 이렇게 변했을 경우 할아버지 노드의 부모 노드가 검은색이라면 상관이 없지만 빨간색이면 다시 빨간색 노드가 빨간색 노드를 자식으로 가지지 못하는 규칙을 위반하게 됩니다.


그러나 저희는 일단 할아버지, 부모, 새로 추가한 자식 이렇게 3개의 노드만 레드블랙 트리의 규칙을 준수하도록 변환하고 그 다음 할아버지 노드의 색이 바뀜으로써 깨지게 되는 레드블랙 트리의 규칙은 다시 할아버지 노드가 새로 추가한 노드로 보면서 루트노드로 거슬로 올라가면서 재귀적으로 규칙을 적용해주면 됩니다.


즉 3대까지 규칙을 준수하도록 변환->다시 할아버지 노드를 새로 추가한 노드로 생각해서 그 노드가 1) 2) 3) 중 어떤 경우에 해당하는지 판단 후 각 경우에 따라서 변환->만약 할아버지 노드와 할아버지 노드의 부모노드가 규칙을 준수한다면 이 때는 재귀의 탈출조건 이렇게 재귀적으로 구성할 것이기 때문에 지금 생각할 것은 3대까지만 생각해서 각 경우에 따라 재구성 해주면 됩니다^^


2) 삼촌 노드가 검은색이며 새로 추가한 노드가 부모 노드의 오른쪽 자식인 경우

이러한 경우에는 부모노드를 기준으로 좌회전 연산을 해주어 3)의 경우로 바꾸어 줍니다. 즉

이런식으로 바뀌어 3)번의 경우로 넘어가게 됩니다.


3) 삼촌 노드가 검은색이며 새로 추가한 노드가 부모 노드의 왼쪽 자식인 경우

이 경우에는 부모 노드를 검은색, 할아버지 노드를 빨간색으로 칠한 다음 할아버지 노드를 기준으로 오른쪽으로 회전 시킵니다.

이렇게 바꾸면 연속되는 빨간 노드가 없기 때문에 4번 빨간 노드의 자식으로 빨간노드가 올수 없다는 규칙은 만족시킬 수 있지만 5번 루트노드에서 모든 잎노드까지의 검은색 노드 수는 같다는 5번 규칙은 깨지게 됩니다. (위의 그림에서 부모 노드의 오른쪽 서브트리 경로의 검정 노드 수가 왼쪽 서브트리 검정노드 수보다 1개 더 많다.)


따라서 추가로 새로 추가한 노드를 바로 검은색으로 바꾸어 주면 이제 5번규칙 까지 만족시키면서 또 여기서 반복 조건은 탈출하게 됩니다.(여기서 다시 재귀로 드갈 필요가 없는게 3대 세대의 루트노드가 검은색이므로 그 3대 세대 루트노드의 부모가 빨간색이든지 검은색이든지 규칙을 위반하지는 않음) 즉

최종적으로 이와 같이 변하게 됩니다.


흑 오늘 소스코드까지 포스팅 하려고 했는데 생각보다 시간이 조금 걸리네요 ^^;;


다음에는 노드 삭제시 트리가 재구성 되는 과정과 소스코드까지 올리겠습니다!