[ Open Data Structures ] - Red-Black Tree - 5

Deletion

삭제에 관한 내장 함수들은 비교적 구현하기가 어렵습니다. 천천히, 침착하게 Node를 삭제하며 마주치는 모든 상황을 따져가면서 공부합니다.

삭제에 관한 기본적이고 1차적인 과정은 Binary Search Tree에서 사용했던 Splice를 수행하는 것과 같습니다. 삭제하려는 node x의 Data를 node x의 Right subtree에서 가장 작은 Node u의 Data와 바꾼 후에, x의 데이터를 갖고 있는 노드 u를 삭제하는 것입니다. 물론, Binary Search Tree의 성질에 의해 x 의 Left Subtree에서 가장 큰 값을 x와 교환해도 큰 상관은 없지만 여기선 전자의 방법을 채택합니다. Splice(x)의 경우, 하나 또는 하나 이하의 Child node를 가진 Node x를 삭제하는 과정이었다는 점을 상기하면 좋겠습니다. 하지만 RBT는 단순히 여기서 그치는 것이 아니라 각 Node의 Colour를 통해 Balancing을 해야하기 때문에 함수의 구현이 까다로워지기 시작하고 막 머리가 아픕니다.

삭제한 node x의 색이 Black이었다면 x의 Parent node의 Black-Height에 변화가 생기는 것은 자명합니다. 임시방편으로써 x의 색을 u에 더해주는 식으로 방어를 할 수 있지만 만약 u와 x가 모두 Black이었다면 x.colour + u.colour = 2가 되어버리고 정의되지 않은 colour value를 가지게 됩니다. 또한 Left-Leaning 성질까지 위반할 여지가 생깁니다. 따라서 이 과정까지는 미봉책이라고 할  수 있으며 이를 고려하여 Tree를 Balancing할 내장 함수 RemoveFixUp을 구현해야만 합니다.

첫 번째 If statement은 삭제하려는 item이 없는 경우를 가리킵니다. FindLastNode는 _item을 Data로써 갖고 있는 Node를 Return하거나 _item이 존재하지 않으면 어떤 Leaf Node의 parent node를 Return합니다. 따라서 nil을 Return한 경우는 RBT자체가 아무런 정보를 갖고 있지 않은 상태이며 *u->Data != _item인 경우는 RBT내에 삭제할 Item이 존재하지 않는 경우입니다. 이 두 경우를 제외하면 u는 적어도 RBT내부에 존재하는 어떤 Node를 가리키게 됩니다.

삭제할 정보를 갖고 있는 Node는 u였습니다. 여기서 u의 right child를 w로 잡고 w가 nil인 경우엔 삭제할 node를 w로 가리키고 삭제할 node의 right child를 u로 가리키게 만듭니다. 하지만 삭제할 node u의 right child가 어떤 Subtree를 가지고 있다면 Right subtree에서 가장 작은 Node의 Data를 삭제할 Data를 가진 Node u의 Data로 옮겨주고 삭제할 node를 잡고 있던 node u를 가장 작은 node의 right child를 가리키게 만듭니다. 이로써, 두 번째 If statement는 if와 else이후 같은 상태의 node w, u의 모습을 갖추게 됩니다. 

이 If statement가 끝난 시점에서 node w가 잡고 있는 것은 삭제할 Data를 갖고 있는 Node입니다. 따라서, node w를 Splice함으로써 Node w를 떼어내고 w의 colour를 u에 합쳐줌으로써 위에서 말했던 미봉책 상태를 갖춘 것입니다. 더 이상 w엔 볼 일이 없기 때문에 delete[] w를 호출하여 불필요하게 붙잡고 있는 메모리를 해방합니다. 진짜 고생은 시작도 안 했습니다. RemoveFixUp은 크게 네 가지의 다른 경우를 고려하여 구현합니다.

※지금부터는 기본적으로 삭제한 Node x의 colour를 합한 node 또는 Parameter로 전달한 Node를 u라고 하겠습니다.

위의 내장 함수에서 보는 것처럼 기본적으로 삭제한 node w->colour + child node _u->colour > 2인 경우에서만 검토를 진행하기 때문에 앞으로 진행하는 논의에서 u의 색이 Red인 경우는 고려하지 않아도 됩니다. 마지막에 Left-Leaning 성질을 위반하는지만 체크를 해주면 됩니다.

Case 0 : node u가 Root node일 경우. 이 경우는 큰 가공 없이 그저 색을 Black으로만 주면 끝입니다. if statement 가장 먼저 검증하고 있는 모습을 상단의 코드에서 확인할 수 있습니다.

Case 1

Case 1은 이렇게 Double black node를 완벽히 처리하지는 않는다.

Case 1: u의 sibling node v가 Red일 경우. 이때 Sibling은 무조건 u의 Parent node x의 left child일 수밖에 없습니다. 이 사실은 RemoveFixUp의 첫 While문의 조건을 통해 확인할 수 있습니다. 기본적으로 While문에 들어가 이 Case들을 검사한다는 것은 내장한 Colour가 0과 1을 넘어섰다는 것입니다(1을 초과하는 색은 double black이라 부르기로 합니다). 그렇다면 이 함수를 호출하기 전에 Splice한 x의 colour와 합하는 과정에서 초과했다는 뜻인데 이는 u와 x가 모두 Black(1)이었다는 것을 보증합니다. 따라서 RBT의 세 번째 성질 Left-Leaning에 의해 u가 black이고 x의 left child라면 u의 Sibling인 v는 w의 Right child가 되고 v는 반드시 Black이어야 했습니다. 즉, 적어도 node v는 right일 수는 없습니다.

이 경우엔 u에 대해 FlipRight를 수행합니다. 그러나 위의 표에서 보는 것처럼 u의 double black 성질은 사라지지 않았습니다. new u로 표현한 까닭은 Case 1을 한 번 처리하고 난 u는 초기에 parameter로 받은 u가 아니기 때문입니다. 사실 Case 1은 Case 3로 곧장 이어지는데 이는 나중에 다시 다루기로 합니다. 아직 double black node인 u를 return 했기 때문에 RemoveFixUp의 while문을 빠져나오지 못하고 double black node u에 대한 검증은 Case에 따라서 계속 됩니다. 여기서 대충 각 Case가 Return하는 Node가 Iterator처럼 작동한다는 사실을 알 수 있습니다.

Case 2

Case 2. node u의 Sibling node를 black인 v라고 하면 node u는 u의 parent node w의 left child이고 v는 w의 right child인 상황을 처리합니다. u->parent w에 대해 PullBlack(w)를 수행하면 각 children node의 색을 하나씩 빼기 때문에 u는 double black(2)에서 black(1)이 되고 v는 red(0)가 됩니다. 하지만 parent node w가 반드시 Red라는 보장이 없기 때문에 w는 이 작업 수행 이후 double black이 될 가능성이 있습니다. 적어도 w는 Red가 아닙니다. 문제는 이것만이 아니라 u가 black이 되고 v가 red가 되었기 때문에 Left-Leaning 성질을 위반합니다. 명시적으로 언급한 적은 없었지만 FlipLeft(w)는 Left-Leaning위반 Node를 해결합니다(곰곰이 생각해보면 자명한 일입니다.). 

FlipLeft(w)를 수행하면 w는 Red가 됩니다(FlipLeft는 w와 Child node의 색을 교환하고 Rotate를 수행했음을 떠올리도록 합니다. 특히, 여기선 FlipLeft를 수행했으니 Right child인 v의 Red와 색이 바뀌었습니다. 추가로 현재 각 node u, w, v가 어떤 관계를 가지고 있는지를 명확히 파악하는 것이 좋습니다). 이제 node v는 u와 w를 포함하는 Subtree의 root가 되었습니다. 여기서 w가 No-Red-Edge를 위반하는지 어떤지를 판단할 것인데 이는 w의 right child q의 colour을 통해 판단할 것입니다. 만약 q가 black이라면 w는 No-Red-Edge를 위반하지 않는 것이고 Node pointer u를 Node pointer v를 가리키게 만들고 Iterator로써 Return하여 다시 RemoveFixUp을 수행합니다.

하지만 여기서 끝나면 고생이라고 하지도 않았습니다. q가 red인 경우가 있을 수 있습니다. 이땐 No-Red-Edge를 명백히 위반합니다. 심지어 Left-Leaning까지 위반할 여지가 있습니다. w가 Red인 것은 w->left가 Black이란 사실을 함축하고 있기 때문입니다. Left-Leaning을 위반하는 가능성은 RotateLeft(w)를 호출함으로써 해소할 수 있지만 No-Red-Edge는 이 방법으론 해결할 수가 없습니다. RotateLeft(w)를 호출한 이후라면 q는 v의 left child이고 w는 q의 left child이며 q와 w모두 Red인 상태가 됩니다. 게다가 v는 바로 이전 문단에서 설명했던 것처럼 Black이거나 Double black인 상태입니다. 총체적 난국이지만 천천히 해결해봅니다.

FlipRight(v)는 q를 v와 w의 Parent node로 만듭니다. 곧바로 PushBlack(q)을 호출하면 v와 w를 모두 Black으로 만들며 q를 원래 색으로 되돌려놓습니다. 놀랍게도 Double black은 사라졌고 No-Red-Edge와 Black-Height 두 성질 중 하나라도 위반하는 Node는 존재하지 않게 되었습니다. 여전히 한 가지의 문제가 여전히 남아있는데 v의 right child가 Red일 수 있으며 Left-Leaning 성질을 위반할 가능성이 존재한다는 사실입니다. 이 일말의 가능성까지 검토한 이후에 만약 필요하다면 FlipLeft(v)를 수행하고 나서야 마침내 다음 작업으로 넘길 수 있습니다.

Case 3. 이 경우는 u의 Sibling node v가 black이고 u가 parent node w의 right child인 경우입니다. 작업을 시작하기에 앞서 가장 먼저 PullBlack(w)를 호출합니다. u는 Double black이며 v는 Black이었으니 PullBlack은 node를 각각 Black, Red로 만듭니다. 곧장 FlipRight(w)를 호출하여 v를 w와 u를 포함한 Subtree의 root node로 만듭니다. 이 시점에서 w는 Red일테고 w의 left child q의 colour에 따라 분기하여 함수를 작성하기로 합니다.

Node 외부에 둘러친 검은 원은 Colour에 +1을 주는 것이다. 따라서 Black node가 추가로 원형 띠를 두르고 있다면 Double Black을 나타낸다.

만일, q가 Red라면 Case 2의 단계와 좌우대칭인 모습이 나타나고 그 방법을 대칭인 채로 처리하면 됩니다. 오히려 Case 3가 Case 2보다 간단한데 그것은 Case 2가 v에 대해 Left-Leaning을 검증했었지만 Case 3는 그럴 필요가 없기 때문입니다.

더 환장할 노릇인 상황은 q가 Black인 경우입니다. 이 경우엔 v의 Left child까지 검증해야 합니다. 만약 v의 Left-Child가 Red라면 단순히 double black의 가능성(적어도 Red일 수는 없다)이 있는 v를 PushBlack(v)을 호출하여 해결할 수 있습니다.

v의 Left child가 Black이라면 Left-Leaning을 위반하는 경우이므로 FlipLeft(v)를 호출하여 이를 해결합니다. 최후에 이 v를 Return하여 다시 Iterator에 이 Node v를 Node u로써 돌려주어 검증을 반복합니다.

마침내 Red-Black Tree의 Remove Operation을 내장하는 작업을 끝마쳤습니다. RemoveFixUp(u)에서 node u에 대한 각 Iteration은 Constant time으로 해결됩니다. 각 Case들을 유심히 살펴보면 u가 root node인 Case 0는 언제나 while문을 빠져나오고 Case 1은 한 번 돌면 반드시 Case 3로 이어지고 Case 3 역시 모든 가능성에 대해서 While문을 깨고 나오는 모습을 확인할 수 있습니다.

따로 이 RBT의 높이에 관한 이야기를 했었는데 높이는 최대 2log(n+1)을 넘을 수가 없었습니다. Big-O Notation으로 O(logn)에 해당하며 RemoveFixUp이 u로부터 Root node로 올라가며 검증한다는 점을 바탕으로 이 내장 함수가 O(logn)내에서 해결된다는 것을 알 수 있습니다.

이것으로 Red-Black Tree를 코드로 구현하는 작업은 마무리합니다.

Full source code 

: HiddenWriter/UnbalancedBinarySearchTree at master (github.com)