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

---

**Contents**

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

---

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

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

**<mark>💡레드 블랙 트리 핵심 요약본:</mark>**

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): 트리에서 노드를 삭제하거나 삽입할 때, 형제 노드의 색상이 중요하게 작용한다. 형제 노드의 색상에 따라 회전 또는 색상 변경이 결정된다.

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729338996785/f2769316-bc2a-4ec5-b759-c67e729d2871.png align="center")

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

---

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

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

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

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

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

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

---

**레드 블랙 트리의 개념** ⬇️

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729339382011/c7be3896-6909-4bf6-9f43-712bf14bcae8.png align="center")

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

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

---

**레드 블랙 트리의 규칙** ⬇️

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

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

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729339445961/72ca78ec-d453-48c3-897f-d9fa371bac2b.png align="center")

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729339873541/f834b88d-5fbc-4939-a834-6f1cf839877c.png align="center")

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340001123/64ea7dd8-ed28-4dac-88f2-eccd792a5d3c.png align="center")

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340163089/b509feff-e374-4a88-a88e-b50d13b41621.png align="center")

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340170348/51332b2a-bbeb-4b79-ad9c-c7ea722a5fd9.png align="center")

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

#### 노드들 간의 관계 정의:

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

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340447736/bf730352-eab8-4fb5-872c-d8cda1a6bfac.png align="center")

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340483346/5d08ae25-7801-49b9-a454-65558bfbb4db.png align="center")

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340685599/ac693a1c-2ce6-4ec1-88d6-0c6c57a98b10.png align="center")

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340725577/ab621159-7bd3-4648-baed-c81b45a9a7ce.png align="center")

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340863672/de0d7432-288d-4169-a610-f5de82161ceb.png align="center")

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

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

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

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

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729340988207/1dd141a4-ade6-4744-89c5-d6fc0b008ea1.png align="center")

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

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

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

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

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729342641542/f761d5ca-e851-40b7-9fc1-a0ef93f4b585.png align="center")

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

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

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

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

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729342780542/6242bdf5-3e10-4eb3-b63e-d0d00d018b2a.png align="center")

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

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

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729342831858/837e077f-6d2c-4391-a89c-2fd1c395665c.png align="center")

#### 1\. **이진 검색 트리 삭제**:

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

#### 2\. **경우의 수 나누기**:

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

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

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

---

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

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729343151478/6561cfd1-3e54-4f09-82e7-6bd4f96feb55.png align="center")

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729403714351/31874aa4-31a5-4ae7-8c8b-83bed116f0a8.png align="center")

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

---

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

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729403861754/4faa8f91-5ef4-4e69-a505-e087f8db1b4e.png align="center")

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729406832186/75aa44c0-3f60-4018-a7ce-66cbe8f2a0f9.png align="center")

* **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**를 기준으로 회전 및 색상 변경이 필요할 수 있다. 이를 통해 트리의 균형을 유지하고, 규칙을 만족시킨다.
        

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729406852187/4574e65c-a4eb-4358-8258-f7c32a35c57c.png align="center")

* **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가지의 경우** ⬇️

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729407986668/5d10b1e2-f9cf-460a-9240-7c012828a5e4.png align="center")

* **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 상세설명** ⬇️

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729408824871/e8a30628-d274-4416-a2b5-6e397e9720e4.png align="center")

### Case 1-1:

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

### Case \*-2:

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729408831948/a5dc9634-7088-4e9d-b220-07a9cb25a396.png align="center")

### 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 상세설명** ⬇️

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729408842066/ef504c65-2a5c-4377-8548-4e954a602b26.png align="center")

### Case 2-4 설명:

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

---

## **학습 정리**

**이진 검색 트리 학습 정리**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729408901747/3ecbe0d5-ef17-4946-8cf6-43935548f5d1.png align="center")

**세그먼트 트리 학습 정리**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729408885234/dee143eb-0c8a-45de-85d7-8b668397306d.png align="center")

**레드 블랙 트리 학습 정리**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729408869142/2e74ebb5-1350-4268-b4d2-e8cc7a482b8f.png align="center")