
레드-블랙 트리는 이진 탐색 트리의 일종으로, 각 노드에 색깔을 부여함으로써
트리의 균형을 유지하는 특징을 가지고 있다.
1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다.
(NIL: null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 어떤 노드의 색깔이 빨간색이라면, 그 노드의 자식 노드들의 색깔은 검은색이다.
5. 모든 리프 노드에서 Black Depth는 같다.
(리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.)
=> Red-Black Tree는 이러한 특징들을 트리의 균형을 유지하며,
이를 통해 트리의 높이를 최소로 유지한다.
따라서 검색, 삽입, 삭제 등의 연산을 빠르게 처리할 수 있다
<aside> 🪧 Info. 리프 노드(Leaf node) 란? 리프 노드는 트리 자료구조에서 가장 아래쪽에 위치한 노드를 말한다. 이는 자식 노드를 가지지 않는 노드를 의미하며, 트리의 가장 끝에 위치하게 된다.
일반적으로 이진 트리에서 리프 노드는 왼쪽 자식과 오른쪽 자식이 모두 없는 노드를 가리키게 된다. 이렇게 리프 노드는 트리에서 데이터를 저장하는 노드로 주로 사용되며, 트리의 모든 정보는 리프 노드에 저장되거나 리프 노드를 통해 엑세스될 수 있다.
Red-Black Tree에서는 NIL노드라고 부르는 특별한 리프 노드를 사용한다. 이 NIL 노드는 일반적인 노드와 달리 키 값을 가지지 않으며, 모든 NIL노드는 블랙으로 색칠된다. 이렇게 NIL노드를 사용함으로써 Red-Black Tree는 자체 균형을 유지하는데 도움을 받게 된다.
</aside>
예시를 보며 이해해보자.
Red-Black Tree를 쉽게 이해하려면, 예시를 들어 이해하는게 가장 쉽다.