Red Black Tree

Red Black Tree

Red Black Tree(이하 RB)는 가장 유명하고 많이 사용되는 ‘균형 이진 탐색 트리’ 구조이다.

이름에서 알 수 있듯이 RB의 노드에는 색깔이 있다. 빨간색과 검은색.

한 번 그림을 보자.

검은색 노드와 빨간색 노드가 있다.

리프노드를 보면 NIL이라고 표기가 되어있는데, Python의 None, C의 NULL과 같다.

RB에서는 NIL 노드를 독립된 노드로 표현하고, 해당 노드를 모두 리프 노드라고 부르기로 한다.

Red black Tree에서는 NIL 노드를 리프노드라고 표현. 나머지를 내부 노드라고 표현한다.

Red Black Tree의 조건

Red Black Tree가 되기 위해서는 다섯 가지 조건을 만족해야 한다.

당연한 얘기지만 ‘이진 탐색트리이면서’ 해당 조건들을 만족해야 한다.

1. 모든 노드는 색이 있어야 한다 (Red / Black)

2. 루트 노드는 Black Node여야 한다.

3. 리프 노드는 Black Node여야 한다.

4. Red Node는 두 개의 자식 노드를 가진다. (중요)

   Red Node는 반드시 두 개의 자식 노드가 Black Node여야 한다.

5. 각 노드에서 리프 노드(NIL 노드)로 가는 경로에 있는 Black Node의 수는 항상 같아야 한다.

   위 그림을 예로 들면, 18번 노드에서 NIL 노드로 가는 경로의 Black Node 수는 어디로 가던 항상 같다.

여기까지 왔을 때, 이런 생각이 든다.

대체 이 짓거리를 왜 해야할까? 이 트리의 장점이 무엇인가?

설명을 하기 위해서 다음과 같이 용어를 정의한다.

H(v) = V의 높이 (height)

bH(v) = V에서 리프노드로 갈 때 만나는 Black Node의 개수 (black height)

• v는 제외하고 리프노드로 갈 때 만나는 Black Node의 개수를 센다.

이제부터 아래 사실을 증명하겠다. 내부 노드는 NIL 노드를 제외한 노드라는 것을 상기하자.

V의 서브트리의 내부 노드 개수 >= 2^bH(v) - 1

증명은 H(v), V의 Height에 대한 귀납법(induction)으로 할 수 있다.

Base Case : H(v) = 0

H(v)가 가장 작을 때는 0이다. 높이가 0이라는 것은 리프 노드밖에 없다는 것이다.

리프 노드는 NIL node이다. NIL node는 Black이다.

즉, bH(v)는 0이다.

H(v) = 0 일 때, bH(v) = 0이다.

v의 서브트리의 내부 노드 개수는 0일 것이다.

2^bH(v)는 2의 0승으로, 1일 것이다.

즉, 0 = 0으로 위의 공식이 성립한다.

Hypothesis : H(v) <= k

H(v)가 특정한 수 K보다 작거나 같은 높이에 대해서…

| v의 서브트리 | >= 2^bH(v) - 1

이라고 가정해보자.

가정이기 때문에 증명할 필요는 없다.

Induction : H(v) = k + 1일 때 성립함을 증명

해당 부분은 유튜브 강의를 참고하면 좋을 것 같다.

그려보려고 했는데 재능이 모자라서 링크로 대신한다.