Red-Black tree delete

안녕하세요 대학생개발자입니다.

 

저번 글에 이어서... 레드블랙트리에 대해서 얘기를 해보려고 합니다.

생각보다 포스팅간의 텀이 길어졌는데요... 제가 실수로 다만들어놓고 삭제를 해버리는바람에 ^^...

다시만들었답니다^^^^

 

그래도 다행인게 한번 만들어 보니까 그다음에 만들때는 금방 만들더라구요... 그와 동시에 이해도도 조금 상승한 것 같습니다...

 

바로 시작하도록 하겠습니다.

 

우선 삭제과정까지는 이진탐색트리와 동일합니다.

 

삭제노드의 자식이 하나이하일 케이스에서는 자기 노드를 바로 삭제하고 아래노드로 연결시켜주면 끝납니다.

 

삭제노드의 자식이 둘일경우에는

 - 오른쪽 자식중 가장 작은 노드를 삭제하면서 그 값을 타겟에 넣거나

 - 왼쪽 자식중 가장 큰 노드를 삭제하면서 그 값을 타겟에 넣는 방법이 있습니다.

 

저는 후자로 선택했구요. 그건뭐 본인 취향에 따라 하시면 될 부분인 것 같습니다.

 

그럼 이제부터 레드블랙 트리의 리밸런싱 작업에 대해서 얘기해보겠습니다.

 

아까 상황에서 진짜로 삭제된 노드( 양쪽의 노드가 닐이 아닐경우)에는 진짜 삭제되는 노드가 왼쪽의 가장 큰값이 되니까 그 노드를 타겟으로 잡으시고 밸런싱 작업을 진행해주시면 되겠습니다.

 

즉 정리를 해보면 선조건으로 최종으로 삭제되는 노드는 자식이 하나 이하여야 됩니다 물론 이케이스에서 nil노드는 제외되는 겁니다.

 

그리고 삽입과 마찬가지로 내가 좌측에 위치해있는지 혹은 우측에 있는지에 따라서 큰 분기 두개로 나눠질겁니다.

안나누셔도 되지만 그렇게하는것보다 저는 큰 분기 두개를 놓고 하는게 가독성이 좀더 좋다고 생각해서 큰 분기 두개로 쪼개놨습니다.

 

제가 정리하고있는 부분에서 케이스는 삭제되는 노드가 왼쪽에 있다는 조건을 걸고 하기때문에 반대의 케이스는 정확하게 반대로만 작성한다면 큰 문제가 없을 것 같습니다.

 

먼저 삭제노드가 레드인경우에는 추가적인 작업이 필요가 없어집니다.

당연하겠지만 레드블랙트리의 5번규칙 루트노드로부터 모든 리프노드까지 경로의 블랙노드 갯수가 동일해야되기 때문에 블랙이 삭제되는 경우에만 리밸런싱의 케이스에 해당합니다. 이런경우는 그냥 if문 하나로 걸러버리시면 됩니다.

 

추가로 레드 노드가 삭제된 케이스라면 위의 노드도 블랙이고 아래의 노드도 블랙입니다.

즉 4번규칙 레드의 자식은 블랙이어야된다 규칙에도 위반되지 않으므로 편하게 삭제하시면 됩니다.

 

자 그럼 여기부터는 반복적으로 검사를 해야되는 부분입니다.

 

1. 삭제 노드의 부모와 자식이 모두 레드인 경우

이 경우에는 심플합니다. 그냥 자식을 블랙으로 바꿔버리면 되기때문입니다.

왜냐면 자식이 자기 자리에 올라오게 될 것이고, 상황만 본다면 위의 레드 노드가 하나 삭제된 케이스와 동일하기 떄문입니다.

다음과 같이 자식이 레드라면 그 자식을 레드에서 블랙으로 바꿔주는 케이스입니다.

 

2 삭제 노드의 형제가 레드인 경우

이 경우에는 한번에 해결할 수는 없습니다.

왜냐면 양쪽의 밸런스가 다르기 때문인데요.

부모의 블랙을 내릴수도 없습니다. 이미 내가 블랙이기 때문에 블랙을 내린다 해도 어차피 삭제노드 쪽에 블랙이 하나 부족한것은 동일하기 때문입니다.

그때 필요한것은 형제 노드쪽의 블랙갯수를 유지한 채로 우리쪽에 블랙을 하나 채우는 방법이 필요합니다.

 

형제를 블랙으로 바꾼뒤 부모를 레드로 바꾸고 부모 기준 RotateLeft를 하게되면 다른 케이스에서 처리할 수 있는 상황이 만들어 집니다.

만약 형제가 레드였다면 형제는 블랙 두 자식을 가지고 있게 됩니다.

이때 좌회전을 해서 형제가 부모가 된다면 형제의 왼자식이 내쪽으로 넘어오게 되므로 블랙 하나가 추가되는 상황이 되었습니다.

 

3 삭제 노드의 형제가 블랙이고 형제의 양쪽 자식이 블랙인 경우

형제의 노드를 레드로 바꿉니다.

이렇게 되면 가족 전체에서 블랙이 하나 빠졌기 때문에 할아버지 노드 기준으로 내 부모 노드 방향으로 블랙 -1 상태가 되게되구요... 그렇다면 이제 내 부모를 기준으로 다시 처음부터 처리를 해야됩니다.

부모가 레드인지 블랙인지는 상관없습니다. 만약 부모가 레드이면 블랙으로 바꾸고 끝나기 때문이고 블랙이면 또 다시 이 루틴들을 반복하기 때문입니다.

다음 그림과같이 P기준 좌우의 밸런스는 맞춰졌습니다. P입장에서는 양쪽 노드의 블랙하나가 줄어든 케이스가 되므로 할아버지를 기준으로 좌우 즉 부모와 부모의 형제를 다시 확인해야할 필요가 있겠습니다.

 

4 삭제 노드의 형제가 블랙이고 형제의 왼자식이 레드일때 오른자식이 블랙인 경우

우리는 P를 기준으로 형제 노드 방면에서 블랙을 가져오고 싶습니다만 SL과 SR의 경우에는 그대로이길 원합니다. 그렇기 때문에 S자리에 SL을 넣어줌으로써 SR의 상위에 블랙갯수에 변함이 없게 만들어주고 SL의 경우에도 상위에 블랙 갯수 변화가 없게 만들어 줄겁니다.

 

먼저 형제의 노드를 레드로 만들어주고 형제의 왼쪽 자식을 레드로 블랙으로 만들어줍니다.

그리고나서 형제를 기준으로 RotateRight를 합니다.

그러면 SL과 S의 위치가 바뀌게 되고 색깔도 바뀌게 됩니다. 즉 역할이 바뀌게 되는거죠

그렇게 된다면 과거 S였던 녀석이 SL의 역할을 하게되고 SL이었던 노드가 S의 역할을 하게 됩니다. 그렇게 된다면

P를 기준으로 RotateLeft를 하더라도 과거 SL이었던 S의 상위 블랙 갯수도 과거 S였던 SL노드도 상위 블랙 갯수가 동일하게 유지됩니다.

그리고 이케이스는 5번에서 이어서 행동이 되기 때문에... 지금은 밸런스가 맞지 않습니다.

5번을 위한 사전 준비정도라고 생각하시면 될 것 같아요.

 

 

5 삭제 노드의 형제가 블랙이고 형제의 오른자식이 레드인 경우

 

이 케이스는 형제의 자식이 레드이기 때문에 형제쪽에 블랙을 추가하고 내쪽에 블랙을 하나 넘기는 상황입니다.

부모의 컬러를 형제에 넣었기 때문에 Rotate이후 부모의 컬러는 동일할것이구요. 부모의 컬러를 black으로 바꿨으니 내 쪽 노드의 블랙이 1 증가되었고 블랙이었던 형제가 부모역할을 하면서 형제라인의 블랙이 1개 줄어든 케이스입니다. 하지만 레드인 자식을 블랙으로 바꿔서 해결한 케이스가 되는것입니다.

 

형제의 컬러를 부모의 컬러로 변경하고 부모의 컬러를 블랙으로 바꾸고 형제의 오른자식을 블랙으로 바꾼뒤 부모를 기준으로 RotateLeft를 해주면 됩니다.

 

 

 

넵... 실행영상인데 일단 실험했을때 큰 문제가 안보이긴합니다. 하지만 몇 백건 몇만건 몇 십만건 삽입후에 문제가되는지 확인하기 위해 따로 std::set과 비교를 하는 프로그램 작성을 해서 테스트 중에있습니다...

일단은 당장 눈에 보이는건 문제가 없어보입니다.

 

뭐 이정도면 된것 같습니다.

다들 긴 글 봐주셔서 감사합니다.

다음번에는 아마... 다시 이 자료구조들이랑 길찾기 알고리즘을 이용해서

서버에 대해서 얘기해보지 않을까 싶습니다.

그럼 안녕히계세요