레드-블랙 트리(Red-Black Tree) ?
- [ ]
레드-블랙 트리는 이진 탐색 트리(BST, Binary Search Tree)의 일종으로, 자기 균형 이진 탐색 트리 중 하나이다 !
- [ ] 삽입, 삭제 등의 연산을 수행할 때 트리의 높이가 한쪽으로 치우치지 않도록 자동으로 균형을 유지한다 !
균형을 유지할 수 있는 이유 ?
- [ ]
레드-블랙 트리의 각 노드는 빨간색 또는 검은색 중 하나를 가진다.
→ 이 색을 이용해 트리의 균형을 유지하며, 몇 가지 규칙을 따라 트리의 구조가 형성되는 것이다.
레드-블랙 트리의 규칙
- 각 노드는 빨간색 또는 검은색이다.
- 루트 노드는 항상 검은색이다.
- 모든
리프 노드(NIL 노드, 즉 null)는 검은색이다.
( 일반적으로 트리 구현에서 리프 노드는 실제 데이터가 없는 null로 간주한다고 한다. )
- 빨간색 노드의 자식은 항상 검은색이어야 한다.
→ 즉, 빨간색 노드가 연속으로 나타날 수 없다.
→ 이 규칙을
레드-레드 규칙이라고 합니다.
- 어느 노드에서든 그 노드로부터 자손
리프 노드까지 가는 모든 경로에서 만나는 검은색 노드의 수는 같아야 한다.
→ 이 규칙이 트리의 균형을 유지하는 데 중요한 역할을 하는 것 !
- [ ] 위 규칙들은 트리의 균형을 강제하여, 트리가 한쪽으로 치우치는 것을 방지하고, 트리의 최대 높이를
O(log n)으로 유지하도록 한다 !
레드-블랙 트리의 연산 (색 변경, 회전)
삽입
- 새로운 노드를 삽입할 때, 그 노드는 기본적으로 빨간색으로 추가됩니다.
→ 삽입 후 트리의 규칙을 위반하는 경우, 적절한 색 변경 또는 트리 회전을 통해 규칙을 복구하고 균형을 유지한다.