Tree in Algorithms (2/2) : Red Black Tree

Contents

1️⃣ 레드 블랙 트리 (Red Black Tree)

1️⃣ 레드 블랙 트리 (Red Black Tree)

💡Keyword: log n 시간 복잡도, 이진 검색 트리의 대안, 회전 연산(Rotation Operation)

💡레드 블랙 트리 핵심 요약본:

1. 노드 색상 (Node Color) : 레드 (Red)와 블랙 (Black) 두 가지 색상 중 하나를 가진다. 이 색상은 트리의 균형을 유지하는 데 중요한 역할을 한다.

2. 블랙 높이 (Black Height): 루트 노드부터 리프 노드까지의 경로에서 만나는 블랙 노드의 개수이다. 모든 리프 노드까지의 블랙 높이는 동일해야 트리의 균형이 유지된다.

3. 균형 유지 (Balancing): 레드 블랙 트리는 삽입과 삭제 시에도 스스로 균형을 유지하는 자기 균형 이진 검색 트리이다. 이를 위해 색상 변경과 회전(rotation)이 수행된다.

4. 회전 (Rotation): 트리의 균형을 유지하기 위해 사용하는 좌회전(Left Rotation)과 우회전(Right Rotation)이 있다. 삽입 및 삭제 과정에서 트리가 불균형해질 때 사용된다.

5. 레드 규칙 (Red Rule): 레드 노드는 두 개의 레드 자식을 가질 수 없다. 즉, 연속된 레드 노드는 허용되지 않는다.

6. 블랙 규칙 (Black Rule): 각 리프 노드까지 가는 모든 경로는 동일한 수의 블랙 노드를 가져야 한다. 이를 통해 트리의 균형이 유지된다.

7. 루트는 항상 블랙 (Root is Always Black): 트리의 루트 노드는 항상 블랙이어야 한다. 이는 트리의 전체 균형을 유지하는 중요한 규칙이다.

8. 삽입 후 재조정 (Rebalancing after Insertion): 새로운 노드를 삽입한 후 트리의 균형이 깨지면 색상 변경과 회전을 통해 트리의 균형을 다시 맞춘다.

9. 삭제 후 재조정 (Rebalancing after Deletion): 노드를 삭제하면 트리의 균형이 깨질 수 있으며, 이를 해결하기 위해 색상 변경과 회전을 사용해 트리의 블랙 높이를 맞춘다.

10. 더블 블랙 (Double Black): 노드를 삭제할 때 발생하는 특별한 상태로, 이 상태를 해결하기 위해 형제 노드와 부모 노드의 색상을 변경하거나 회전을 수행한다.

11. 형제 노드 (Sibling Node): 트리에서 노드를 삭제하거나 삽입할 때, 형제 노드의 색상이 중요하게 작용한다. 형제 노드의 색상에 따라 회전 또는 색상 변경이 결정된다.

레드 블랙 트리의 개념 - 이진 검색 트리의 효율 ⬇️

💡요약: 이진 검색 트리는 많은 알고리즘에서 기본적인 자료 구조로 활용되지만 불균형된 이진 검색 트리는 시스템의 전체 성능을 저하시키게 된다. 현업에서 대부분의 응용 프로그램에서는 AVL 트리, Red-Black 트리와 같은 균형 트리를 사용하는 것이 중요하다. 이러한 트리는 스스로 균형을 맞추기 때문에 최악의 경우에도 log⁡ n 시간 복잡도를 보장하기 때문이다.

이진 검색 트리의 효율:
- 이진 검색 트리의 효율은 트리의 깊이에 따라 달라다.
- 비효율적인(편향된) 트리에서는 전체 노드 수가 한쪽으로 치우치면, 최악의 경우 검색 시간이 Θ(n) (선형 시간)까지 걸릴 수 있다.
- 균형 잡힌 트리에서는 검색 시간이 평균적으로 Θ(logn) (로그 시간)으로 줄어든다.
비교 시각화:
- 왼쪽 그림은 매우 비효율적인 트리(편향된 트리)를 보여주고 있다. 모든 노드가 한 줄로 연결되어 있어 검색 시간이 매우 길어지게 된다.
- 오른쪽 그림은 균형 잡힌 트리로, 보다 빠르게 검색이 가능하다.

레드 블랙 트리의 개념 - 이진 검색 트리의 대안법
(Alternative to Binary Search Tree - Red-Black Tree) ⬇️

💡요약: 레드 블랙 트리는 자주 불균형 상태로 변하는 데이터를 다룰 때 적합하다. 삽입과 삭제가 빈번하게 발생하는 경우에도 성능을 일정하게 유지하기 때문이다. 데이터베이스, 파일 시스템 등에서 사용된다. 또한 회전 연산(rotation operation)을 통해 트리의 균형을 유지하는데, 이러한 연산은 복잡해 보이지만 성능 최적화에 매우 중요한 역할을 한다는 점을 알아두자.

그렇다면 레드 블랙트리는 어떤 면에서 이진 검색 트리와 다를까? 자세히 알아보자

💡중요: 불균형된 이진 검색 트리의 단점을 극복하는 레드 블랙 트리

이진 검색 트리: 노드 삽입 순서에 따라 편향적일 경우O(n)의 성능 (비효율)
레드 블랙 트리: 스스로 균형을 잡는 이진 검색 트리로 O(log n)의 성능 (효율)

레드 블랙 트리는 삽입과 삭제 시 균형이 맞지 않으면 회전 연산을 통해 스스로 트리의 균형을 유지해 나간다.
이진 검색 트리에 비해 삽입과 삭제가 복잡하지만 최악의 경우에도 일정한 검색 시간을 보장하므로 실무에서 효율적으로 쓰이고 있다.
레드 블랙 트리는 유사한 균형 트리인 AVL 트리에 비해 덜 엄격한 규칙을 적용하여 회전 연산이 적다.

레드 블랙 트리의 개념 ⬇️

모든 노드에 일정한 규칙에 맞게 블랙 또는 레드의 색을 칠하는 이진 검색 트리

레드 블랙 트리는 모든 노드가 레드 또는 블랙의 색을 가지며, 이를 통해 트리의 균형을 유지한다.
Key Point: 레드 블랙 트리에서의 리프 노드(leaf node)는 일반적인 리프 노드와는 달리 NIL이라는 특수 노드로 가정한다. 이 NIL 노드는 검정색으로 칠해져 있으며 트리의 균형을 맞추기 위한 역할을 한다.

레드 블랙 트리의 규칙 ⬇️

레드 블랙 트리는 모든 노드에 다음과 같은 규칙에 맞게 칠을 한다.

루트는 블랙이다.
모든 리프는 블랙이다.
노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (이 규칙으로 인해 트리의 높이가 log n에 가깝도록 만들어 성능을 보장하게 된다)
💡중요: 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. (이 규칙으로 인해 트리의 균형을 보장하게 된다. 블랙 노드의 수를 맞춰줌으로써, 트리가 특정 방향으로 한없이 길어지는 것을 방지하기 때문이다. )

4번 추가 설명: 레드 블랙 트리에서는 여러 경로가 있을 수 있다. 예를 들어, 루트에서 특정 왼쪽 리프 노드로 가는 경로가 있고, 루트에서 오른쪽 리프 노드로 가는 경로가 있을 수 있다. 각 경로마다 노드의 수가 다를 수 있지만, 각 경로에서 거치는 블랙 노드의 개수는 같아야 한다. 이 규칙 덕분에 트리는 너무 한쪽으로 치우치지 않고 균형을 유지할 수 있게 된다.

레드 블랙 트리의 개념 - 레드 블랙 트리의 변환 ⬇️

이진 검색 트리:
- 처음에는 단순한 이진 검색 트리이다. 트리의 각 노드가 단일 색(보통 흰색)으로 표시되며, 노드의 삽입 순서에 따라 트리가 형성되어 있다. 하지만, 이 트리는 균형이 맞지 않을 수 있다.
레드 블랙 트리로 변환:
- 두 번째 단계에서는 이진 검색 트리를 레드 블랙 트리로 변환하는 과정이 진행된다. 각 노드에 레드 또는 블랙 색상이 할당되며, 트리의 균형을 유지하기 위해 NIL 노드도 추가되었다.
- 레드 블랙 트리의 규칙에 따라, 루트 노드는 블랙이고, 리프 노드는 모두 블랙이다. 또한, 레드 노드의 자식은 반드시 블랙이어야 하며, 경로마다 동일한 수의 블랙 노드를 만나게 된다.
리프 노드를 하나로 처리:
- 마지막 단계에서는 각 경로의 끝에 있는 리프 노드들이 하나의 NIL 노드로 처리되어 균형을 유지하게 되었다. 이 과정은 불필요한 리프 노드를 하나의 NIL로 처리하여 트리의 균형을 유지하고 효율적인 탐색을 가능하게 한다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 검색 ⬇️

💡요약: 레드 블랙 트리에서 검색은 이진 검색 트리와 동일하게 작동하며, 트리의 색상은 검색 성능에 영향을 미치지 않는다.

레드 블랙 트리의 검색은 노드의 색깔과 무관하며, 이진 검색 트리와 동일하다.

레드 블랙 트리에서 검색 연산은 일반적인 이진 검색 트리와 동일하게 이루어진다.
노드의 색깔(레드 또는 블랙)은 검색 연산에는 영향을 미치지 않는다.
검색 시 트리의 구조만을 사용하여, 왼쪽 자식 노드는 현재 노드보다 작고, 오른쪽 자식 노드는 크다는 규칙을 따른다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입의 과정 ⬇️

💡요약: 레드 블랙 트리에서 새로운 노드는 이진 검색 트리처럼 삽입되고, 레드로 칠해진 후 규칙 위반 여부에 따라 재조정(수선, Adjustment)된다. 이를 통해 트리의 균형을 유지하고 성능을 보장한다.

이진 검색 트리와 동일한 삽입 방식: 레드 블랙 트리에서 새로운 노드를 삽입할 때, 일반 이진 검색 트리처럼 삽입 위치를 찾아서 노드를 추가한다.
삽입된 노드를 레드로 칠함: 새로 삽입된 노드는 항상 레드로 칠해진다. 이때 레드 블랙 트리의 규칙을 어기지 않는지 확인해야 한다.
규칙 위반 시 수선: 삽입된 노드로 인해 레드 블랙 트리의 규칙이 위반될 경우, 트리의 균형을 유지하기 위해 재조정(수선, Adjustment)이 이루어진다. 이 과정에는 색 변경, 회전(Rotation Operation) 등의 연산이 포함될 수 있다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입 후 조정 과정 설명⬇️

💡요약: 레드 블랙 트리에서 삽입된 노드가 루트가 되면, 반드시 블랙으로 변경되어 트리의 균형을 유지한다.

삽입 노드 X: 새로운 노드 X가 트리에 삽입되며, 레드 블랙 트리의 규칙에 따라 기본적으로 레드로 칠해진다.
삽입 노드가 루트일 경우: 만약 삽입된 노드가 트리의 루트가 되면, 레드 블랙 트리의 규칙(루트는 항상 블랙이어야 함)에 따라 삽입된 노드를 블랙으로 변경해야 한다.
레드에서 블랙으로 바꿈: 삽입된 노드가 루트가 되었으므로 레드에서 블랙으로 색깔을 변경해, 트리의 균형을 맞춘다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입 후 조정 과정 설명 2⬇️

💡요약: 레드 블랙 트리에서 삽입된 노드가 루트가 아닐 때는 부모, 조부모, 삼촌, 형제의 관계를 고려하여 트리의 균형을 유지하는 추가 연산이 필요하다.

삽입된 노드가 루트가 아닐 때 어떤 요소들을 고려해야 하는지를 알아보자

노드들 간의 관계 정의:

X (삽입 노드): 새로 삽입된 노드.
p (부모): X의 부모 노드.
p² (조부모): p의 부모, 즉 X의 조부모 노드.
S (삼촌): p의 형제 노드, 즉 X의 삼촌 노드.
y (형제): X의 형제 노드.

레드 블랙 트리의 규칙에 따른 삽입 후 처리:

삽입된 노드 X가 트리의 루트가 아닌 경우, 레드 블랙 트리의 규칙을 유지하기 위해 부모(p), 조부모(p²), 삼촌(S), 형제(y) 노드의 관계를 고려한다,
p가 p²의 오른쪽 자식인 경우에는 대칭적으로 처리합니다. 이 말은 반대 방향의 트리에서도 유사한 규칙이 적용된다는 뜻이다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입의 상황; 부모가 레드라면?⬇️

💡요약: 부모가 블랙일 경우, 규칙이 유지되므로 추가 작업이 필요하지 않다. 부모가 레드일 경우, 규칙 위반이 발생하며, 조부모와 삼촌의 색상에 따라 트리 재조정이 필요하다.

1. 부모가 블랙인 경우 → 규칙 만족

위의 이미지에서는 부모 노드(p)가 블랙이다.
이 경우, 레드 블랙 트리의 규칙이 만족되므로 추가적인 조정이 필요하지 않다.
부모가 블랙일 때는 삽입된 노드 X가 레드여도 문제가 없기 때문에 트리의 균형이 유지된다.

2. 부모가 레드인 경우 → 규칙 위반

위의 이미지에서는 부모 노드(p)가 레드이다. 이 경우 규칙 위반이 발생한다.
- 레드 블랙 트리의 규칙에 따르면 레드 노드의 자식은 반드시 블랙이어야 한다. 하지만 삽입된 노드 X와 부모 p 모두 레드이므로 이 규칙을 위반하게 되었다.
- 부모가 레드일 경우, 조부모(p²)는 항상 블랙이어야 하며, 삼촌(S)의 색깔도 중요하게 작용한다. 삼촌이 블랙이면 회전 연산이 필요할 수 있고, 레드라면 색상 변경을 통해 규칙을 만족시킬 수 있다.
- 이 상황에서는 조부모는 블랙이고, 삼촌(S)이 블랙일 경우 추가적인 재조정이 필요하다. 트리의 균형을 맞추기 위해 회전 및 색상 변경 등의 연산이 진행된다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입의 상황; 부모가 레드라면 삼촌은? ⬇️

💡요약: 삼촌이 레드인 경우, 부모와 삼촌의 색을 블랙으로 바꾸고, 조부모를 레드로 변경하여 규칙을 유지한다. 삼촌이 블랙인 경우, 회전 연산을 통해 트리의 균형을 맞추며 색상 재조정이 필요할 수 있다.

1. 삼촌이 레드인 경우 (위 그림)

상황: 부모 p와 삼촌 S가 모두 레드인 경우.
- 이 경우, 부모와 삼촌이 모두 레드이므로 규칙 위반이 발생하였다. 규칙에 따르면, 레드 노드의 자식은 반드시 블랙이어야 하기 때문이다.
처리 방식:
- 부모(p)와 삼촌(S)의 색상을 블랙으로 변경해야 한다.
- 그리고 조부모(p²)는 레드로 변경된다.
- 조부모에서 다시 규칙을 적용하여 트리의 균형을 유지한다. 이는 트리의 상위로 올라가면서 재귀적으로 처리될 수 있다.

2. 삼촌이 블랙인 경우 (위 그림)

상황: 삼촌 S가 블랙인 경우.
- 이 경우, 삼촌이 블랙이므로 회전 연산을 통해 트리의 균형을 잡을 필요가 있다.
처리 방식:
- 회전 연산을 수행하여 트리의 균형을 맞춘다. 일반적으로 왼쪽 회전이나 오른쪽 회전이 사용된다.
- 회전 후에도 트리의 규칙이 만족되도록 부모와 조부모의 색상 조정이 일어날 수 있다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입 후 처리 과정 : 부모가 레드, 삼촌이 레드인 경우? ⬇️

💡요약: 부모와 삼촌이 모두 레드인 경우, 부모와 삼촌을 블랙으로, 조부모를 레드로 변경하여 규칙을 다시 만족시킨다. 조부모는 삽입 노드처럼 재귀적으로 규칙을 적용받으며, 트리의 균형을 유지한다.

1. 위배된 초기 상황 (왼쪽 그림):

삽입된 노드 X의 부모(p)와 삼촌(S)이 모두 레드이다.
이 상황은 레드 블랙 트리의 규칙(레드 노드의 자식은 블랙이어야 함)을 위반하고 있다.
규칙을 위반한 상황에서는 삽입 후 트리의 균형을 맞추기 위해 추가적인 처리가 필요하다.

2. 부모, 삼촌, 조부모의 색상 변경 (오른쪽 그림):

부모(p)와 삼촌(S)의 색상을 블랙으로 바꾼다.
조부모(p²)의 색상은 레드로 변경된다.
이 과정을 통해 노드 간의 레드-블랙 관계를 재조정하여 규칙을 만족시킨다.

3. 조부모를 삽입 노드로 재귀적 적용:

조부모(p²)가 다시 삽입 노드처럼 처리된다. 이 상황에서도 규칙 위반이 발생할 수 있으며, 이 경우 상위로 재귀적으로 올라가면서 규칙을 적용하게 된다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입 후 처리 과정 : 부모가 레드, 삼촌이 블랙인 경우? ⬇️

💡요약: 회전 연산(Rotation Operation)필요, X가 오른쪽 자식일 경우 왼쪽 회전을 통해 트리의 균형을 맞추고 X가 왼쪽 자식일 경, 오른쪽 회전을 통해 트리의 균형을 맞춘다.

위 이미지는 삽입된 노드 X가 부모 p의 왼쪽 자식인지 오른쪽 자식인지에 따라 처리 방식이 달라지는 두 가지 상황을 설명하고 있다.

1. X가 p의 오른쪽 자식인 경우 (왼쪽 그림):

상황: 삽입된 노드 X가 부모 p의 오른쪽 자식인 상황이다. 부모 p는 레드이고, X는 레드이다. 이때 레드-블랙 트리의 규칙을 위반하게 되었다.
처리 방식:
- 이 상황에서는 왼쪽 회전 연산이 필요할 수 있다. X가 오른쪽에 위치할 경우 트리의 균형을 맞추기 위해 X와 부모 p를 회전시켜 위치를 조정한다.
- 회전 후 부모와 조부모 간의 관계를 재조정하여 트리의 규칙을 유지한다.

2. X가 p의 왼쪽 자식인 경우 (오른쪽 그림):

상황: 삽입된 노드 X가 부모 p의 왼쪽 자식인 경우이다. 이 경우에도 부모와 자식이 모두 레드인 상태로, 레드 블랙 트리의 규칙을 위반하였다.
처리 방식:
- 이 상황에서는 오른쪽 회전 연산이 필요할 수 있다. X가 왼쪽에 위치할 경우 트리의 균형을 맞추기 위해 X와 부모 p를 오른쪽 회전시켜 트리의 균형을 맞춘다.
- 이후에도 부모와 조부모 간의 관계가 조정되어 트리의 규칙을 만족시키게 된다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입 후 처리 과정 : 부모가 레드, 삼촌이 블랙, x가 오른쪽 자식인 경우? 상세설명 ⬇️

1. X가 p의 오른쪽 자식인 초기 상황 (왼쪽 그림):

위에서 언급된 회전연산을 자세히 다뤄본다.
삽입된 노드 X는 부모 p의 오른쪽 자식이다. 부모 p와 자식 X 모두 레드인 상태로, 이는 레드 블랙 트리의 규칙을 위반하는 상황이다.
삼촌 S는 블랙이다. 따라서 부모와 자식의 색을 수정하는 것만으로는 규칙을 회복할 수 없고, 회전 연산이 필요하게 된다.

2. 부모 p와 X에 대한 회전 (오른쪽 그림):

왼쪽 회전을 통해 X와 부모 p의 위치를 변경하였다. X가 부모 p의 자리를 차지하게 되고, p는 X의 왼쪽 자식이 된다. 이렇게 왼쪽 회전을 적용함으로써 트리의 균형을 맞출 수 있다.

3. 회전 후 재조정 (오른쪽 그림 3번):

회전 후, 트리의 균형을 다시 맞추기 위해 부모 p와 조부모 p² 간의 관계를 재귀적으로 조정할 수 있다. 이 과정에서는 추가적인 회전 또는 색상 변경이 필요할 수 있다.

레드 블랙 트리의 검색과 삽입 - 레드 블랙 트리의 삽입 후 처리 과정 : 부모가 레드, 삼촌이 블랙, x가 왼쪽 자식인 경우? 상세설명 ⬇️

💡요약: X가 부모의 왼쪽 자식일 경우, 트리의 규칙을 유지하기 위해 오른쪽 회전이 필요하다. 회전 연산은 트리의 균형을 유지하는 데 필수적인 과정이다. 또한 삼촌의 색상에 따른 차이도 중요한데 삼촌이 블랙일 때는 회전 연산을 통해 문제를 해결한다. 삼촌이 레드일 경우에는 색상 변경을 통해 문제를 해결할 수 있다.

1. X가 p의 왼쪽 자식인 초기 상황 (왼쪽 그림):

위에서 언급된 회전연산을 자세히 다뤄본다.
삽입된 노드 X는 부모 p의 왼쪽 자식이다. 부모 p와 자식 X 모두 레드인 상태로, 이는 레드 블랙 트리의 규칙을 위반하는 상황이다.
삼촌 S는 블랙이다. 이러한 경우 회전 연산을 통해 트리의 균형을 유지해야 한다.

2. 조부모 p²와 부모 p에 대한 회전 (오른쪽 그림):

오른쪽 회전을 통해 부모 p와 조부모 p²의 위치를 변경하였다. 이때, p는 조부모 p²의 자리를 차지하고, 조부모는 오른쪽 자식으로 이동한다. X는 그대로 p의 왼쪽 자식으로 남는다.
이러한 오른쪽 회전을 통해 트리의 균형을 맞추고 규칙을 유지할 수 있다.

레드 블랙 트리의 삭제의 과정 ⬇️

💡요약: 노드 삭제는 이진 검색 트리와 동일하게 진행되며, 삭제 후 발생할 수 있는 여러 경우의 수에 따라 추가적인 처리가 필요하다. 이진 검색 트리와 다른 점은 색상 변경과 회전 연산을 통해 삭제 후에도 트리의 균형을 유지하여 레드 블랙 트리의 규칙을 보장한다.

1. 이진 검색 트리 삭제:

삭제 과정은 이진 검색 트리의 노드 삭제와 동일하다. 삭제할 노드를 찾아서 트리에서 제거하는 기본적인 과정은 이진 검색 트리의 삭제 과정과 같다.

2. 경우의 수 나누기:

노드 삭제 시 발생할 수 있는 다양한 경우의 수를 나눈다. 삭제 후 트리의 균형이 유지되는지, 규칙 위반이 있는지에 따라 처리 방식이 달라질 수 있다.

3. 각각의 경우에 따른 처리:

각 경우에 맞는 처리 방법을 적용하여 트리의 규칙을 유지한다. 규칙을 위반하는 상황에서는 색상 변경이나 회전 연산을 통해 트리의 균형을 맞출 수 있다.

레드 블랙 트리의 삭제 - 레드 블랙 트리의 삭제의 가정⬇️

💡요약: 레드-블랙 트리에서 노드를 삭제할 때, 자식이 없거나 하나인 경우 제한된 처리가 가능하다. 자식이 둘인 경우, 오른쪽 서브트리에서 직후 원소를 찾아서 교체하고 삭제하며, s의 규칙 위반 여부를 봐야하는데 s는 왼쪽 자식이 없다.

💡중요포인트: 오른쪽 서브트리에서 직후 원소를 찾는 방법과 그 원소를 삭제하는 과정, 노드의 자식 수에 따른 삭제 규칙이해

특정 노드 삭제 시 자식이 없거나 한 개만 있는 경우:
- 이 경우에는 제한된 처리가 가능하다는 점을 강조하고 있다.
자식이 둘인 경우:
- 자식을 둘 가진 노드를 삭제하는 경우에는, 오른쪽 서브트리에서 직후 원소를 가진 노드 s을 찾아서 교체한 뒤, s를 삭제한다.
s에 대한 규칙:
- s의 규칙을 지켜야 하는데, 슬라이드에서 설명된 대로, s는 왼쪽 자식이 없다는 점이 중요하다. 그림에서는 이를 시각적으로 보여주고 있으며, 노드 30을 찾아서 삭제하는 과정을 나타내고 있다.

레드 블랙 트리의 삭제의 상황 - 자명한(obvious) 경우⬇️

💡요약: 여기서 "자명하다"는 뜻은, 특정 상황에서는 별다른 추가 작업이나 복잡한 조정 없이 규칙을 만족할 수 있다는 것을 의미한다. 즉, 레드-블랙 트리의 균형이나 속성 유지가 간단히 해결된다는 뜻이다. 레드 노드를 삭제하면 트리 규칙이 자동으로 만족된다. 블랙 노드를 삭제하고 그 자식이 레드인 경우, 자식을 블랙으로 승격하면 트리 규칙이 유지된다.

왼쪽 (삭제 노드가 레드인 경우):
- 삭제할 노드 m이 레드일 경우, 트리의 속성상 규칙을 자동으로 만족한다. 별도의 추가 조정 없이 노드를 바로 삭제할 수 있다.
- 레드 노드를 삭제했을 때는 레드-블랙 트리의 속성 중 하나인 경로상의 블랙 노드 수가 변하지 않기 때문에 트리의 구조는 균형을 유지하게 된다.
오른쪽 (삭제 노드가 블랙이고 유일한 자식이 레드인 경우):
- 삭제할 노드 m이 블랙이고, 유일한 자식 노드 x가 레드일 경우, 자식 노드를 블랙으로 승격시켜 규칙을 만족시킨다. 이를 통해 트리의 블랙 노드 균형을 유지할 수 있게된다. 이 상황에서도 규칙 위반 없이 삭제를 처리할 수 있다.

레드 블랙 트리의 삭제의 상황 - 부모의 색상에 따른 분류 ⬇️

레드-블랙 트리에서 삭제할 때 부모의 색상에 따라 나눌 수 있는 두 가지 경우를 설명하고 있다. 삭제 후 트리의 균형을 유지하는 데 있어 부모의 색상이 중요한 역할을 하기 때문에 두 가지 케이스로 나누어 설명한다.

💡요약: 부모가 레드인 경우, 삭제 후에도 트리의 균형이 자연스럽게 유지되기 때문에 추가 조정 없이 규칙이 만족된다. 부모가 블랙인 경우, 블랙-높이의 불균형이 생길 수 있기 때문에 트리의 재조정이 필요하다.

왼쪽 (부모가 레드일 경우 - Case 1):
- 삭제한 노드의 부모 노드 p가 레드일 때, 자식 노드 x는 블랙
- 이 경우에는 부모 노드 p가 레드이므로, 트리의 블랙-높이(경로 상의 블랙 노드 수)가 유지되기 때문에 규칙을 위반하지 않는다. 추가적인 복잡한 처리가 필요하지 않다.
오른쪽 (부모가 블랙일 경우 - Case 2):
- 삭제한 노드의 부모 노드 p가 블랙일 때, 자식 노드 x는 블랙이다.
- 이 상황에서는 부모와 자식 모두 블랙이기 때문에, 트리의 블랙-높이 불균형이 발생할 수 있다. 이를 해결하기 위해 추가적인 트리 재조정 작업이 필요하다. 트리의 균형을 맞추기 위해 회전이나 색상 변경과 같은 추가적인 처리가 필요할 수 있다.

레드 블랙 트리의 삭제의 상황 - 부모가 레드 상세설명 ⬇️

💡요약: 부모가 레드이고 형제 노드가 블랙일 때는, 형제 노드의 자식 색상에 따라 회전이나 색상 변경을 통해 블랙-높이의 균형을 유지해야 한다. 각 경우에 따라 적절한 회전과 색상 변경이 이루어져야 트리의 규칙을 위반하지 않고 균형을 맞출 수 있게된다.

Case 1-1:
- 부모 노드 p가 레드, 자식 노드 x는 블랙(-1), 형제 노드 s는 블랙이다.
- 이 경우에는 자식 노드 l과 r이 모두 블랙인 상황으로, 회전이나 색상 변경이 필요할 수 있다. 블랙-높이 조정을 위한 추가 작업이 요구된다.
Case 1-2:
- 부모 노드 p가 레드, 자식 노드 x는 블랙(-1), 형제 노드 s는 블랙, 그리고 형제의 자식 노드 중 하나가 레드이다.
- 형제 노드 s의 오른쪽 자식 r이 레드인 상황이다. 이 경우에는 자식 간 회전 및 색상 변경을 통해 트리의 균형을 맞출 수 있다. 회전을 통해 블랙-높이를 조정하고 트리의 균형을 유지해야 한다.
Case 1-3:
- 부모 노드 p가 레드, 자식 노드 x는 블랙(-1), 형제 노드 s는 블랙, 그리고 형제의 자식 노드 중 하나가 레드
- 형제 노드 s의 왼쪽 자식 l이 레드인 상황으로, 여기서는 형제 노드 s를 기준으로 회전 및 색상 변경이 필요할 수 있다. 이를 통해 트리의 균형을 유지하고, 규칙을 만족시킨다.

레드 블랙 트리의 삭제의 상황 - 부모가 블랙인 경우 상세설명 ⬇️

💡요약: 부모가 블랙일 경우, 트리의 균형을 유지하기 위해 더 복잡한 조정이 필요할 수 있다. 형제 노드의 색상 변경이나 회전을 사용하여 블랙-높이를 맞추는 것이 중요하다.

Case 2-1:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s도 블랙이며, s의 자식들도 모두 블랙이다.
- 이 경우, 트리의 균형을 맞추기 위해서는 형제 노드 s의 색상을 레드로 바꾸는 등의 처리가 필요할 수 있다. 하지만 부모의 블랙-높이 문제는 여전히 남아 있어 추가 조정이 요구될 수 있다.
Case 2-2:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s는 블랙, 그리고 형제의 자식 r이 레드이다.
- 이 경우는 r을 블랙으로 만들고 s를 레드로 바꾸고 회전하는 방법으로 트리의 균형을 맞출 수 있다.
Case 2-3:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s는 블랙, 그리고 형제의 자식 l이 레드인 경우이다.
- 이 상황에서는 형제 s를 기준으로 좌회전을 하여 블랙-높이를 맞추고 트리의 균형을 유지할 수 있다.
Case 2-4:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s가 레드인 경우이다.
- 이 경우에는 형제 s를 블랙으로 만들고 부모 노드 p를 레드로 변경한 뒤 회전을 통해 트리의 균형을 맞출 수 있다.

레드 블랙 트리의 삭제 알고리즘 구현 시 고려해야할 5가지의 경우 ⬇️

💡요약: 레드-블랙 트리에서 삭제 시 고려해야 할 5가지 중요한 케이스는, 부모와 형제 노드의 색상과 구조에 따라 다르다. 각 경우는 부모와 형제 노드의 색상 및 구조에 따라 트리의 균형을 맞추기 위해 다른 알고리즘이 필요하다. 주로 회전과 색상 변경을 통해 레드-블랙 트리의 블랙-높이를 맞추는 작업이 이루어 진다. 삭제 알고리즘에서 가장 많이 발생할 수 있는 케이스들을 다루고 있으며, 이를 처리하기 위한 아래의 5가지 전략을 알아두는 것이 중요하다.

Case 1-1:
- 부모 노드 p가 레드, 자식 노드 x가 블랙(-1), 형제 노드 s가 블랙인 경우
- 이 경우, 추가적인 회전이나 색상 변경 없이 트리의 균형을 유지할 수 있는 간단한 케이스이다.
Case *-2:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s가 블랙, 형제의 자식 r이 레드인 경우
- 이 경우는 형제 노드 r의 색상을 변경하고 트리의 균형을 맞추기 위해 회전이 필요하다.
Case *-3:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s는 블랙, 그리고 형제 노드의 자식 l이 레드인 경우
- 이 상황에서는 형제 노드 s를 기준으로 좌회전을 통해 균형을 맞춘다.
Case 2-1:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s가 블랙이며, 형제의 자식들 역시 모두 블랙인 경우
- 이 경우, 형제 노드 s를 레드로 바꾸는 처리가 필요하다.
Case 2-4:
- 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s가 레드인 경우
- 이 경우는 형제 노드 s를 블랙으로 만들고, 부모 노드 p를 레드로 변경한 후 회전을 통해 트리의 균형을 맞출 수 있다.

레드 블랙 트리의 삭제 알고리즘 구현 케이스 1-1, 케이스 *-2 상세설명 ⬇️

💡요약: Case 1-1은 부모 노드가 레드일 때 추가적인 수정이 필요 없이 트리 균형이 유지된다. Case *-2는 형제 노드의 자식이 레드일 경우 회전과 색상 변경을 통해 트리의 균형을 맞추는 중요한 경우이다.

Case 1-1:

상황: 부모 노드 p가 레드(빨간색), 자식 노드 x가 블랙(-1), 형제 노드 s가 블랙인 경우
처리: 이 경우는 트리의 균형을 유지하기 위한 추가적인 회전이나 색상 변경이 필요하지 않다. 부모 노드 p가 레드이기 때문에 전체적으로 트리의 블랙 높이를 유지할 수 있다.
결과: 트리의 균형이 쉽게 유지된다.

Case *-2:

상황: 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s의 오른쪽 자식 노드 r이 레드인 경우이다.
처리: 이 경우는 트리의 회전과 색상 변경이 필요하다.
1. 부모 노드 p와 형제 노드 s의 색상을 변경합니다.
2. 형제 노드 s의 자식 노드 r을 기준으로 좌회전을 수행하여 트리의 균형을 회복하였다.
결과: 트리의 블랙 높이가 적절히 유지되고 균형 상태로 변환된다.

레드 블랙 트리의 삭제 알고리즘 구현 케이스 *-3, 케이스 2-1 상세설명 ⬇️

💡요약: Case *-3에서는 형제 노드의 자식이 레드일 때 좌회전으로 균형을 맞추는 것이 중요하다. Case 2-1에서는 형제와 그 자식들이 모두 블랙일 경우 형제 노드를 레드로 변경하며, 재귀적으로 문제를 해결해야 한다.

Case *-3:

상황: 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s도 블랙이고, 형제 노드의 왼쪽 자식 l이 레드인 경우이다.
처리: 이 상황에서는 형제 노드 s의 자식 노드 l이 레드이기 때문에 트리의 균형을 유지하기 위해 좌회전을 수행해야 한다.
1. 형제 노드 s를 기준으로 좌회전을 실시한다.
2. 회전 후 트리의 형태는 case *-2와 비슷한 상태가 되며, 이후 추가적으로 균형을 맞추기 위한 처리를 할 수 있다.

Case 2-1:

상황: 부모 노드 p가 블랙, 자식 노드 x가 블랙(-1), 형제 노드 s도 블랙이며, 형제 노드의 자식들(l과 r)이 모두 블랙인 경우이다.
처리: 이 경우는 트리의 블랙 높이가 맞지 않기 때문에 형제 노드 s를 레드로 변경하는 처리가 필요하다. 이로 인해 부모 노드에서 동일한 문제를 재귀적으로 해결해야 할 수 있다..
- 부모 노드 p는 다시 검토가 필요하며, 필요 시 추가적인 회전이나 색상 변경이 이루어질 수 있다.

레드 블랙 트리의 삭제 알고리즘 구현 케이스 2-4 상세설명 ⬇️

💡요약: 형제 노드가 레드인 경우 색상 변경과 회전이 먼저 이루어져야 트리의 균형을 유지할 수 있다. 회전 후 트리가 Case 1-1, Case 1-2, 또는 Case 1-3으로 변환되어, 해당 규칙에 따라 추가적인 처리가 가능할 것이다.

Case 2-4 설명:

상황: 부모 노드 p가 블랙이고, 자식 노드 x가 블랙(-1), 형제 노드 s가 레드인 경우. 이때 형제 노드 s의 자식 l과 r은 모두 블랙이다.
처리: 형제 노드 s가 레드이기 때문에 부모 노드 p와 형제 노드 s의 색상을 변경한 후, 형제 노드 s를 기준으로 우회전을 수행하였다. 이 후, 트리 상태가 이전에 설명한 Case 1-1, Case 1-2, 또는 Case 1-3 중 하나로 전환된다.

학습 정리

이진 검색 트리 학습 정리

세그먼트 트리 학습 정리

레드 블랙 트리 학습 정리

Tree in Algorithms (2/2) : Red Black Tree