Red black Tree

Prerequisite

삽입이든, 삭제든 반드시 BST의 삽입, 삭제를 우선적으로 처리하고 그 다음에 Red-black의 property가 깨지면 그것을 보정하는 방향으로 이해해야 한다. 즉, 만약에 BST의 삽입, 삭제 규칙을 지키면서 처리했는데, Red-black의 property가 깨지는 것이 없다면 그대로 끝내주면 된다.

Insert

1. 해당 트리에 아무것도 없는 경우에는 삽입하는 노드를 검은색으로 칠하고, 그렇지 않은 경우에는 빨간색으로 칠한다.

2.1. 삽입된 노드의 부모가 검은색인 경우 : 이 경우에는 Red-black property가 깨지는 것이 전혀 없으므로 바로 종료한다.

2.2 삽입된 노드의 부모가 빨간색인 경우 : 이 경우에는 Red-black property 중 red-property가 깨지게 되므로, 수정해야 한다.

3. Insert에서 어떤식으로 수정할지는 삽입된 노드 기준으로 부모의 sibling(uncle)을 기준으로 결정된다.

3.1 삽입된 노드 기준으로 부모의 sibling이 빨간색인 경우 : Recoloring을 처리해준다. 즉 조부모를 빨간색으로 칠하고, 그 자식들을 검은색으로 만든다.

좌 : 15를 삽입 했을 때, 우 : Recoloring

단, 조부모를 빨간색으로 만든다는 지점때문에 새로운 문제점이 생길 수 있다. (Red property / Root property)

이 경우에는 다시 1번으로 돌아가 위 과정을 반복해주면 된다. 위 예시 같은 경우에는 Root가 빨간색이 되었기 대문에 10을 결과적으로 검은색으로 다시 바꾸는 작업을 추가적으로 진행해주어야 한다.

3.2. 삽입된 노드 기준으로 부모의 sibling이 검은색인 경우 : Rotation and recoloring (삽입된 노드부터 시작해서 조부모까지 연결한 것을 rotation하고 recoloring한다. recolor하는 것 자체는 직관적이라 쉽게 판단할 수 있다.

40을 추가한 상황, 맨 처음 경우는 3.1의 경우이므로 recoloring만 수행해주었고 이로 인해서 또 다른 문제가 발생하여 이를 3.2를 통해서 해결하는 양상

1줄 요약 : Insert의 경우 반드시 부모의 형제를 보도록 하자.

 

연습 문제 : 10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70을 삽입하는 상황

Delete

다시 말하지만, BST의 삭제를 먼저 수행하고, 지워야할 노드를 선택하는 것이다. 반드시 결과적으로 정말로 지워야하는 노드를 봐야한다.

1. 지워야할 노드가 빨간색인 경우 : 그냥 지운다.

30을 지우기 위해서 실질적으로는 26이 inorder predecessor라서 지워지는 상황, 26에 해당하는 노드의 색깔이 빨간색이므로 그냥 지워지면 됨

2. 지워야할 노드가 검은색인 경우 : Double black이 발생하게 된다. 그래야 depth property가 깨지지 않는다.

검은색인 40이 지워지면서 Double black노드가 만들어짐, 결과적으로 Deletion과정에서 이 Double black를 어떻게 처리할 것인가가 핵심이다.

2.1 Double black이 나타나는 노드가 Root인 경우 : 그냥 종료 (결과적으로 전체적인 black depth가 1개 작아진 상황)

2.2 Double black이 나타나는 노드가 Root가 아닌 경우 : 반드시 Double black이 나타나는 노드의 형제가 어떤 색을 가지고 있는지 확인한다.

2.2.1 Double black이 나타내는 노드의 형제가 검은색

2.2.1.1 형제들의 자식들이 모두 검은색인 경우 : 부모에게 1개의 black을 넘기고, Double black이 나타내는 노드의 형제를 빨간색으로 색칠한다.

15가 결과적으로 삭제되는 상황이다. Double black을 기준으로 형제는 30이고, 30의 자식들은 모두 검은색이다(null은 검은색 취급). 따라서 20을 검은색, 30을 빨간색으로 만들어주면 된다.

주의해야할 지점은 만약, 부모가 이미 검은색인 경우는 Double black이 이동하게 된다. (빨간색인 경우는 그냥 검은색이 되는 것으로 끝난다.) 이와 같은 경우가 발생한다면, 결과적으로 Double black이 위로 전파됨에 따라 2.1이나 2.2를 반복하게 되는데, 계속해서 위로 전파될 수는 없고 최대한 많이 위로 올라가봐야 2.1을 마지막으로 끝나는 수 밖에 없다. 따라서 위와 같은 과정은 유한번만 반복되게 된다. (최대 트리의 높이 : logV).

위에 해당하는 예시를 살펴보도록 하자.

15를 삭제하고 싶은 상황. 이때 15의 색깔이 검은색이므로 Double black이 형성됨. 이때 Double black 기준으로 형제가 검은색이고, 그 자식들이 모두 다 검은색인 상황이다. 따라서 검은색 1개를 부모에게 넘기고, 형제를 빨간색으로 만든다. 그러나 이 과정에서 부모가 Double black이 되는 상황

부모가 Double black이 됨으로 인해서 위와 같은 케이스를 반복하게 된다. 결과적으로 루트가 Double black 케이스에서 종료하게 된다.

2.2.1.2 형제의 자식들 중 Double black과 가까운 노드가 빨간색, 먼 노드가 검은색인 경우

1. Double black의 형제와, 빨간색 자식의 색을 바꾼다.
2. Rotation (Double black 반대 방향으로)
3. 2.2.1.3의 과정을 반드시 수행하게 된다.

1이 결과적으로 지워지는 상황이고, 검은색이므로 Double black이 만들어졌다. Double black 기준 형제 노드가 검은색이고 자식이 모두 검은색이므로 2.2.1.1의 케이스이다.

2.2.1.1의 결과 부모에게 black이 옮겨지고 이로 인해 부모가 Double black 노드가 된 상황이다. 변경된 Double black 기준으로 형제는 검은색이고 가까운 쪽은 빨간색, 먼 쪽은 검은색이므로 2.2.1.2 케이스에 해당한다. 따라서 형제와 빨간색 부모의 색을 바꾸고 회전한다. 위 그림에서 볼 수 있는 것처럼 반드시 2.2.1.3 케이스로 수렴하게 된다.

2.2.1.3 형제의 자식들 중 Double black과 가까운 노드가 검은색, 먼 노드가 빨간색인 경우

1. Double black의 부모와, 형제의 색을 바꾼다.
2. Rotation (Double black 방향으로)
3. Double black 중 1개의 black를 기존의 형제들의 자식들 중 빨간색인 녀석에게 넘겨준다.

80을 지우는 상황이므로 Double black이 형성이 된다. 또한 Doulbe black 기준 형제의 자식들 중 먼 쪽이 빨간색이고 가까운 쪽이 검은색인 상황이므로 2.2.1.3케이스이다. 따라서 Double black의 부모와 형제의 색을 바꾸고 Rotation을 처리한 뒤, 기존의 형제의 빨간색 자식에게 검은색을 넘겨주게 된다.

Double black 기준으로 형제가 검은색이고 가까운 쪽은 검은색, 먼쪽은 빨간색이므로 2.2.1.3케이스이다. Double black의 부모와 형제의 색을 바꾸고

2.2.2 Double black이 나타나는 노드의 형제가 빨간색인 경우

1. Double black의 부모와 Double black의 형제들의 색을 바꾼다.
2. Double black 방향으로 rotation한다. (이 부분은 직관적으로 이해할 수 있다.)
3. 2번부터 다시 확인한다. (결과적으로 leaf쪽으로 내려가기에 언젠가는 종결된다.)

결과적으로 15가 포함된 노드가 지워지는 상황이고, 검은색이므로 결과적으로 Double black이 만들어지게 된다. Double black 기준으로 형제가 빨간색이므로 부모와 형제의 색을 바꾸고 Double black 방향으로 회전한다.

결과적으로 왼쪽과 같은 그림이 만들어지고, Double black를 해결하기 위해서 어느 케이스에 해당하는지를 보아야하는 상황이다. Double black 기준으로 형제가 검은색이고 자식이 모두 다 검은색이므로 2.2.1에 해당한다. 따라서 부모와 형제의 색을 바꾸고 마무리된다.

1줄 요약 : Delete의 경우 문제가 생기는 상황은 Double black이고, Double black의 형제를 보도록 하자.

연습 문제 : 위 그림에서 55, 30, 90, 80, 50, 35, 15를 삭제하는 상황