레드블랙트리 개념
- 레드블랙트리는 이진탐색 트리의 성질을 그대로 따라가는 트리입니다. 즉, 왼쪽 자식 트리는 부모 노드 보다 작아야 하고, 오른쪽 자식 트리는 부모 노드보다 커야 하는 성질을 그대로 이용합니다.
- 다만, 레드 블랙트리는 밸런스드 트리로서 자가균형을 유지하는 성질이 추가 됩니다.
- 밸런스드 트리는 부모 노드를 기준으로 왼쪽 자식 트리와 오른쪽 자식 트리의 높이를 측정했을 때 그 깊이(Depth)가 1이상 차이가 나지 않는 트리입니다.
- → 즉, 레드블랙트리는 깊이가 2이상차이가 나는 경우 자동으로 밸런스드 트리로 균형을 맞추는 트리라고 볼 수 있습니다.
레드 블랙 트리의 규칙
- 모든 노드는 빨간색 혹은 검은색이어야 합니다.
- 루트 노드는 무조건 검은색 이어야 합니다(Root Node → Black).
- 새로 추가된 노드는 무조건 빨간색이어야 합니다( New Node → Red).
- 빨간색 노드는 연달아 두 번 이상 나올 수 없습니다(단, 검은색은 가능).
- 빨간색 노드의 자식은 무조건 검은색 이어야 합니다(Red Node ⇒ (Child) Black).
- 루트 노드에서 각 Null인 리프 노드(NIL)까지 만나는 모든 검은색의 개수는 동일해야 합니다.
<aside>
💡 참고로 레드블랙트리에서 NIL 은 Null 인 노드로서 기본적으로 검은색 노드 입니다. 해당 노드는 데이터 삽입 시 추가되는 노드가 아니라 추가하지 않더라도 아무런 값을 담고 있지 않은 Null 인 노드가 존재함을 가정합니다. 만일, 해당 트리가 레드-블랙 트리인지 판가름 할 때 해당 NIL 까지 개수를 측정해보면 됩니다.
</aside>
<aside>
⚠️ 루트 노드 부터 NIL 까지 지나가는 모든 경로에서 만나는 검은색 노드의 개수를 측정했을 때, 그 개수가 모두 동일해야 합니다. 위 예시에서 13 → 8 → 1→ NIL 인 경우와 13 → 17 → 25 → 22 → NIL 인 경우 모두 동일하게 검은색 노드가 3개 인 것을 볼 수 있습니다. 즉, 검은색 노드의 개수가 동일하지 않은 경로가 존재한다면, 해당 트리는 레드 블랙 트리가 아닌 것입니다.
</aside>
Recoloring(색기) 을 수행할 때 | 나를 기준으로 삼촌 노드가 빨간색 일 때,