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

Red-Black Tree는 2-4Tree를 Binary Search Tree의 역할을 효율적으로 시뮬레이션하기 위해 탄생했습니다. 따라서, 2-4trees 와는 다르게 Children node가 두 개 뿐이며 각 Node가 Red(0) 또는 Black(1) 두 가지 색 중 하나를 갖는 Binary Search Tree라고 볼 수 있습니다. 이 점은 Figure b-1과 Figure b-2를 통해 개략적으로 이해할 수 있습니다. 다음과 같은 Property가 RBT를 논의함에 있어서 언제나 참인 것으로 받아들입니다.

Property 2.1. Root node에서 시작하여 모든 Leaf node까지 이르는 경로 상의 검은색(Black coloured node)의 합은 같다. (Black-height)

Property 2.2. 두 개의 Red coloured node는 인접할 수 없다. (No-red-edge) 약간의 수식을 동원하여 설명하면 Root node가 아닌 어떤 Node u에 대해서 u.colour + u.parent.colour >= 1 이다.

Property 2.2에서 Root를 제외했음에도 불구하고 사실은 RBT에서 Root node 역시 Property 1이나 2를 위반하지 않는 선에서 색을 가질 수 있으며 여기선 언제나 Black을 갖는다고 가정하겠습니다. 어떤 Operation을 수행하여 Root node에 변화가 생기더라도 이 규칙은 언제나 유지합니다.

또한, RBT의 모든 External node 즉 nullptr를 가리키는 모든 node는 black을 갖는다고 가정합니다. 이를 통해서 모든 node는 색을 갖게 되며 Leaf node를 포함한 모든 Internal node는 두 개의 children node를 갖게 됩니다. 아래는 간단한 RBT의 예시입니다. 최상단이 Root node이며 천천히 짚어보면 Red/Black node가 Property 1, 2를 위반하지 않았음을 알 수 있을 것입니다.

Figure a. RBT의 일례로  검은 사각형은 nullptr를 나타낸다.

Figure b-1

Figure b-2

직관적으로 Red-Black Tree는 대응하는 2-4Tree가 존재할 것이라는 생각이 듭니다. 실제로 Figure b-1에 보이는 RBT의 파란 영역은 2-4 Tree에 정확히 대응하는 Node가 존재합니다. 이제, Figure b-1을 참고해서 n개의 node를 가지고 있는 Red-Black Tree를 T라고 표현한 뒤에 다음과 같은 변화를 주었다고 가정해 봅니다.

RBT로부터 (1)모든 red node를 제거한 다음에 (2)이 제거한 node의 children node를, (3)제거한 node의 parent node(무조건 black node일 수밖에 없다)에 children node로 붙입니다. 이렇게 변화를 준 T를 T`이라고 둡니다. T`은 오직 Black node만을 갖게 되었습니다. 이렇게 구성된 T`의 각 internal node는 적어도 두 개 혹은 셋, 넷의 node를 children node로 가지고 있는 상태가 될 것입니다. 변화 이전의 상태를 임의의 internal node가 갖고 있는 children node의 상태에 따라서 나누어 살펴보면, 다음과 같이 정리할 수 있습니다. Figure b-1의 파란 원 부분이 Figure b-2에서 어떻게 변화되었는지 잘 관찰해야 합니다.

2 red, 0 black -> 4개의 children node

1 red, 1 black -> 3개의 children node

0 red, 2 black -> 2개의 children node

이제 RBT의 모든 red node가 사라졌기 때문에 property 2.1( Black Height Property )는 모든 root에서 leaf에 이르는 경로에 대해 성립합니다. 말을 바꾸면 Red node를 제거함으로써 Red-Black Tree T가 2-4 Tree T`로 변환되었다는 소리입니다.

RBT가 n개의 internal node를 갖고 n + 1개의 external node를 갖고 있다고 했을 때, 변환한 2-4Tree는 n + 1개의 Leaves를 가지고 있게 됩니다. 따라서, 이 Tree는 최대 log(n + 1)의 높이를 가지게 됩니다.

2-4 Tree T`에서 root node로부터 시작해서 leaf node에 이르는 경로는 RBT T에서 root node로부터 External node에 이르는 대응합니다. 또 이 경로 상에서 첫 Node와 마지막 Node는 언제나 Black이며 연속된 두 개의 node는 많아봐야 하나만 Red node일 수 있기 때문에(No-red-edge) 이 경로(Path)는 최대 log(n + 1)개 의 Black node를 가지며 최대 log(n + 1) - 1개의 Red node를 갖게 됩니다. 따라서 root node에서 어떤 임의의 internal node에 이르는 가장 긴 경로는 다음과 같습니다.