개구리의 개발 블로그 개구리의 개발 블로그

Red-Black 노드는 모든 경로의 Black 노드의 개수를 동일하게 유지한다. Red-Black Tree는 일반적인 이진 탐색 트리와 다르게 Black 노드의 개수를 통해 균형을 유지한다. Tree에 새로운 노드를 삽입하는 경우를 생각해보자. Black 노드를 삽입이 불가능한 것은 아니다. 중요한 것은 Red-Black 트리의 조건에 맞게 모든 경로에 대하여 동일한 Black Depth를 갖도록 균형을 맞춰주는 것이다. Black 노드를 삽입하면, 언제나 균형이 깨진다. 새로운 노드가 추가되는 경로에만 Black 노드의 개수가 1개 증가하기 때문이다. 반면에 Red 노드를 삽입하는 경우에는 균형이 유지되는 경우가 존재한다. 리프 노드의 부모가 Black 노드인 경우에는 Red-Black 노드의 조건과..