[ Open Data Structures ] - Red-Black Trees - 4

Add operation

Red-Black Tree(이하 RBT)가 기본적으로 지켜야 할 두 가지 Propertise인 Black-Height, No-Red-Edge에 이어 Left-Leaning의 성질을 추가했고 이에 따라 본격적인 Add Operation을 구현합니다. RBT를 구현하는 방법은 여러가지가 있으니 어떤 방법이 더 있는지 확인해보는 것이 좋겠습니다.

RBT에서 Addition을 내장하기 위해서는 가장 먼저 일반적인 Binary Search Tree에서 수행했던 새로운 Leaf node를 추가하는 방식을 채택할 것입니다. 즉 새로운 node u에 데이터 x를 저장하고 Red라는 성질을 추가로 제공하는 것입니다. 하지만 이 글에서 사용하는 방법은 저장할 데이터를 받아 내부에서 Node를 생성하여 추가하기 때문에 BinarySearchTree에서 사용했던 Rotation, Add은 그대로 쓰기가 어렵습니다(Node의 Type이 다르기 때문입니다). 따라서, Code duplication에 가까운 짓을 해야만 합니다. 다채로운 해결방법이 있으나 무시하고 진행합니다.

Red-Black Trees - 2에서 설명했던 것처럼, 어떤 임의의 Leaf node에 이르는 경로 상에 존재하는 Black node의 수는 모두 같아야 합니다. 그렇기 때문에 추가한 Node에 Red라는 성질을 부여함으로써 Black-Height 성질을 당장은 위반하지 않도록 합니다. Red node는 어디에 추가되어도 다른 성질을 위반할지언정 Black-Height property를 위반하지 않기 때문입니다.

그러나, Left-Leaning과 No-Red-Edge는 충분히 위반할 여지가 남아있고 이를 해결하기 위해 다음과 같은 AddFixUp이라는 함수를 사용합니다. 침착하게 하나씩 짚어보며 생각해보도록 합니다. 아래 그림에서 실수한 것이 있는데 추가하려는 Node x는 어떤 곳에서 Node u라고 표기하기도 했기 때문에 혼란스러울 수 있습니다. 기본적으로 두 Node는 완전히 같은 Node입니다.

Node x는 추가하려는 node를 나타냅니다. 그리고 각 case 1-1과 case 1-2는 x의 parent의 left의 colour에 따라 경우를 나눈 것입니다. case 1-1과 case 1-2는 모두 x 자신이 x->parent의 Left Child인 경우를 나타냅니다. 한 가지 추가할 사항이 있는데 RBT의 특성 상 Leaf node는 null pointer로 취급하기는 하지만 사실 null pointer가 아닌 nullptr처럼 행동하는 Node pointer를 추가할 것입니다. 사실, 이 개념은 Binary Search Tree에서부터 사용했어야 할 개념이었기 때문에 다음과 같은 코드를 Binary Search Tree에 추가기로 합니다.

Tree의 성질에 따라 적절히 사용하기로 한다

그렇다면 RBT에선 nullptr역할을 하긴 하지만 Black이라는 성질을 포함해야 하기 때문에 Node를 생성할 때 주의를 기울이기로 합니다. 이는 각 함수를 내장하는 과정에 드러나기 때문에 확인할 수 있습니다.

Case 1-1은 Parent node w가 black이기 때문에 No-Red-Edge 성질을 위반하지 않습니다. 따라서 그대로 Return하여 FixAddUp을 끝냅니다. w의 right child가 black인 경우를 떠올릴 수 있는데 Add가 수행되기 전에 RBT의 모든 성질을 만족하고 있었더라면 해당 자리에 Black이 있을 경우, 새로운 node가 x자리에 추가될 수 없습니다.

Case 1-2는 x의 parent인 w의 colour가 Red인 경우다. 이 경우에 당장 알아차릴 수 있는 위반사항은 No-Red-Edged입니다. '?'node는 어떤 colour를 갖는 Node가 올 지 모른다는 것을 표현한 것입니다. Case 1-2를 처리하기 전에 Case 2를 먼저 소개해야 합니다. 그 이유는 Case 2를 일차적으로 처리하여 Case 1-2와 완전히 같게 만들어 처리과정을 조금이라도 단축하기 위함입니다.

Figure b

Case 1-1과 Case 1-2는 Parent node w가 각각 Black/Red 일 경우를 따져보았습니다. 그러나 합리적으로 생각해보면 추가하려는 node가 Parent node의 left/right 일 두 가지의 가능성을 가지고 있었습니다. Case 1은 x가 w의 Left child일 경우를 따졌으며 Case 2는 Right child였을 가능성을 살펴본 것입니다. Case 2가 특별할 수밖에 없는 이유는 Left-Leaning 성질 때문이다. 만약 w의 left child가 Red였다면 w는 무조건 Black이기 때문에 세 가지 성질 중 그 어떤 것도 위반하는 일이 없고 그대로 작업을 마쳐도 됩니다. 하지만 Figure b에서 보는 바와 같이 현재는 Left-Leaning을 명백히 위반하고 있습니다. 전에 설명한 대로 FlipLeft는 다음과 같은 과정을 포함하고 있습니다.

'Parent node colour와 right child node colour를 교환하고 RotateLeft를 수행한다.'

마지막으로 u=w는 Rotation의 영향으로 뒤바뀐 w와u를 부모-자식 관계를 다시 복원시키는 역할을 합니다. 더 자세히 설명하자면 Case 2를 Case 1-2와 완전히 같은 생태를 만들어 FixAddUp을 수행하겠다는 뜻입니다. 이렇게 가공된 Case 2의 결과를 보면 Case 1-2와 똑같다는 것을 알 수 있습니다. 물론 parent node w의 색은 다를 수 있습니다. Case 2에서 w가 Black이었다면 Case 1-2와 완전히 같은 결과일 테지만 w가 Red인 상태였다면 다른 모습으로 작업이 끝났을 것입니다. 다음을 더 살펴보도록 합니다. 바로 이 내용이 나옵니다. w의 colour에 따라 두 가지의 경우로 갈라집니다.

Figure c

바로 위에서 논의한 대로 Case 2에서 w의 색에 따라 Case 3로 이어졌습니다. Case 2에서 w가 Black이었다면 Case 3-2로 이어져 작업이 완료됩니다. 하지만 Case 1-2의 결과와 완전히 같은 Case 2에서 w가 Red인 경우는 Case 3-1로 이어져서 다시 추가적인 작업을 요구하는 상태에 이르게 됩니다.

Figure d

지금껏 등장하지 않았던 GrandParent Node가 등장했습니다. 난리가 났습니다. g로 표현했으며 Case 3-1을 처리하는 과정입니다. node g의 색에 따라 Black : case 4-1 / Red : case 4-2로 분리했습니다. FlipLeft의 대칭이 FlipRight이기 때문에 특별히 설명할 것은 없는 것 같습니다.

Case 4-1을 조금 더 다세히 풀어본 그림

Case 4-2의 경우엔 또 다시 a,b 두 가지의 상황을 상정해야 한다. Case 4-2-a의 경우는 node w가 g의 left subtree일 경우입니다. g->right의 node를 uncle이라고 했을 때, uncle node의 각 children node는 black node일 것이 RBT의 세 가지 성질에 의해 자명합니다. Uncle도 나오고 더 난리가 났습니다! 따라서, RBT의 세 가지 성질을 만족하는 임의의 Red Node를 Black Node로 바꾸었을 경우에 어떤 위반도 일어나지 않는다는 점을 바탕으로 node g에 대해 PushBlack을 수행하면 Case 4-2-a의 경우 작업을 반쯤 완료시킬 수 있습니다. node g는 black이라는 점은 현재 No-Red-Edge의 위반을 유발한 Node가 w가 아닌 u라는 점에서 자명합니다. w는 RBT의 모든 Properties를 만족하고 있었기 때문에 Node g는 반드시 Black일 수밖에 없습니다.

마지막 Case 4-2-b입니다. w가 g의 Right subtree일 경우인데 사실은 Case 4-2-a와 크게 다른 것이 없습니다. 그림에 표기하는 것을 깜빡했는데 이 과정이 마무리되고 u=g로 놓고 다시 이 작업을 수행해야만 하는데, 그 이유는 Black에서 Red로 바뀐 g가 g->parent에 대해 다시 No-Red-Edge를 위반할 가능성이 존재하기 때문입니다. 따라서 Case 4-2-a가 반쯤 완료되었다 표현한 것입니다!

무슨 생각으로 만든 자료구조일까요?