WEEK05 - TIL Red-Black Tree (레드 블랙 트리) - 1

Red-Black Tree : 가장 많이 사용되는 균형 이진 탐색 트리

NIL = c언어에서는 NULL / 파이썬에서는 None을 의미하는 노드를 말하는 것

앞에 트리를 설명할 때 none값에 대해 그림상 표현하지 않는다 (아무것도 없기 때문에) 하지만 RBtree에서는 독립된 노드로 그린다. 그리고 이 노드를 '리프 노드(leaf)'라고 부른다. 리프 노드를 제외한 노드를 '내부 노드'라고 한다.

 

RBtree는 다음의 5가지 조건을 만족해야만 한다. [당연히 이진 탐색 트리]

1. 모든 노드는 Red나 Black의 색깔이 있어야 한다. (둘중에 하나 무조건)

2. 루트 노드는 무조건 Black이어야 한다.

3. 리프 노드 또한 무조건 Black이어야 한다.

4. red node는 두 개의 자식 노드를 갖는데, 그 자식 노드 모두 색깔이 Black이어야 한다.

    (근데 Black노드의 자식은 아무거나 상관이 없다.)

5. 각 노드에서 leaf 노드로 가는 경로들이 많은데, 그 중 Black 노드의 수가 항상 같아야 한다.

    ex. 25에서 leaf노드까지 4가지 경우의 경로가 존재하고 그 4가지는 모두 정확히 같은 Black node(2개씩)를 가지고 있다.

    ex. 루트노드인 13부터 leaf노드까지 11가지의 경로가 존재하고, 그 경로에 포함된 Black node 개수는 3개로 다 똑같다. == 따라서 해당 이미지는 RBtree가 맞다! 🙆‍♀️

 

- h(v) = v의 높이(height)

- bh(v) = (black height) v에서 leaf node로 갈 때 만나는 Black node의 개수는 동일한데, v는 제외하고 leaf node로 가면서 만나는 black node의 개수를 말한다.

    ex. bh(13) = 2 인데, 이유는 v는 카운트 하지 않기 때문에 13을 제외한 black node의 개수는 2개이다.

    ex. bh(25) = 1

    ex. bh(17) = 2 얘는 빨강이라 어차피 카운트 x

 

사실 증명하기

= v의 서브 트리의 내부 노드(NIL 노드 제외한 정상적인 노드) 개수는 최소 2^bh(v) - 1개는 존재한다.