(2부) 레드블랙트리(red-black tree)의 삭제는 어떻게 동작할까요? 시간 복잡도는 어떻게 될까요? AVL 트리와 차이는 무엇일까요? 이 영상으로 후련하게 해결하세요 :)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

레드 블랙 트리에서 노드 삭제 시 삭제되는 노드의 자녀가 없거나 하나라면 해당 노드의 색이 '삭제되는 색'이며, 자녀가 둘이라면 삭제될 노드의 후속자(successor) 색이 '삭제되는 색'이 됩니다.

'삭제되는 색'이 레드일 경우 레드 블랙 트리의 어떤 속성도 위반하지 않으므로 추가 조정이 필요 없지만, 블랙일 경우에는 2번, 4번, 5번 속성을 위반할 수 있어 재조정이 필요합니다.

블랙이 삭제되어 5번 속성을 위반했을 때, 삭제된 노드의 위치를 대체한 노드에 '엑스트라 블랙'을 부여하여 더블 블랙 또는 레드 앤 블랙 노드를 만들고, 이 노드들을 4가지 케이스 분류를 통해 해결함으로써 레드 블랙 트리의 속성을 다시 만족시킵니다.

레드 블랙 트리 삭제의 큰 그림

레드 블랙 트리의 삭제 과정은 **일반적인 이진 탐색 트리의 삭제 방식과 동일하게 시작**됩니다. 삭제 전에는 레드 블랙 트리의 속성을 만족해야 하며, 삭제 후에는 속성 위반 여부를 확인하고, 위반 시 재조정하여 다시 속성을 만족하도록 해야 합니다. 핵심은 삭제 후 속성 위반 여부를 어떻게 효율적으로 확인할 것인지입니다.

레드 블랙 트리에서 **노드를 삭제할 때, 어떤 색의 노드가 '삭제되는 색'인지 파악하는 것이 속성 위반 여부를 확인하는 데 매우 중요**합니다. 이는 삭제하려는 노드의 자녀 유무에 따라 달라집니다.

삭제하려는 노드의 **자녀가 없거나 하나일 경우, '삭제되는 색'은 삭제되는 노드 자체의 색**입니다. 예를 들어, 자녀가 없는 25(레드)를 삭제하면 레드가 삭제되고, 자녀가 없는 80(블랙)을 삭제하면 블랙이 삭제됩니다. 자녀가 하나인 40(블랙)을 삭제하는 경우에도 블랙이 삭제됩니다.

반면에 **삭제하려는 노드의 자녀가 둘일 경우, '삭제되는 색'은 해당 노드의 석세서(successor) 노드의 색**입니다. 예를 들어, 20(레드)을 삭제할 때 자녀가 둘이므로 20의 석세서인 25(레드)가 20의 자리를 대체하며, 이때 25의 색깔인 레드가 삭제됩니다. 마찬가지로 35(블랙)를 삭제할 때는 석세서인 37(레드)의 레드가, 50(레드)을 삭제할 때는 석세서인 80(블랙)의 블랙이 삭제됩니다.

삭제되는 색에 따른 속성 위반 여부

**삭제되는 색이 레드라면 레드 블랙 트리의 어떠한 속성도 위반하지 않습니다.** 레드 노드의 삭제는 블랙 경로 수에 영향을 주지 않으며, 레드-레드 연속 규칙이나 루트 노드, 닐 노드 규칙에도 위반되지 않기 때문입니다.

하지만 **삭제되는 색이 블랙이라면 2번(루트 노드는 블랙), 4번(레드 노드의 자녀는 블랙), 5번(블랙 경로 수 동일) 속성을 위반할 수 있습니다.** 예를 들어, 40(블랙)을 삭제하면 5번 속성 위반(블랙 경로 수 불균형)과 4번 속성 위반(레드-레드 연속)이 발생할 수 있습니다. 35(블랙)를 삭제하면 루트 노드가 레드가 되어 2번 속성을 위반할 수 있습니다.

블랙 삭제 후 재조정: 엑스트라 블랙의 도입

삭제되는 색이 블랙이어서 속성을 위반했을 경우, 특히 5번 속성(블랙 경로 수 동일)은 까다롭습니다. 이를 해결하기 위해 **삭제된 노드의 위치를 대체한 노드에 '엑스트라 블랙'을 부여**합니다. 이 엑스트라 블랙은 경로에서 하나의 블랙으로 카운트되어 5번 속성을 다시 만족시킵니다.

만약 삭제로 인해 루트 노드가 레드가 되는 2번 속성 위반이 발생했다면, **해당 루트 노드를 블랙으로 바꿔주면 해결**됩니다. 그러나 대부분의 블랙 삭제는 5번 속성 위반을 초래하며, 이때 엑스트라 블랙이 사용됩니다.

**엑스트라 블랙이 부여된 노드는 그 노드의 원래 색깔에 따라 '더블 블랙' 또는 '레드 앤 블랙'으로 불립니다.** 예를 들어, 10(블랙)을 삭제하면 그 자리를 대체한 닐 노드에 엑스트라 블랙이 부여되어 더블 블랙이 됩니다. 30(블랙)을 삭제하면 30의 자리를 대체한 25(레드)에 엑스트라 블랙이 부여되어 레드 앤 블랙이 됩니다. 50(블랙)을 삭제하면 석세서인 80(블랙)의 자리를 대체하는 닐 노드에 엑스트라 블랙이 부여됩니다.

레드 앤 블랙 및 더블 블랙 해결 방안

**레드 앤 블랙 노드는 단순히 블랙으로 색깔을 변경하면 해결됩니다.** 이는 5번 속성을 이미 만족하고 있으며, 4번 속성 위반 문제도 동시에 해결되기 때문입니다.

**더블 블랙 노드의 해결은 엑스트라 블랙을 없애는 것이 핵심**이며, 이는 총 4가지 케이스로 분류됩니다. 이 케이스 분류는 더블 블랙 노드의 형제 색깔과 그 형제의 자녀들 색깔에 따라 결정됩니다.

**케이스 4: 더블 블랙의 오른쪽 형제가 블랙이고, 그 형제의 오른쪽 자녀가 레드일 때.** 이 경우, 오른쪽 형제의 색깔을 부모의 색깔과 같게 만들고, 부모와 오른쪽 형제의 오른쪽 자녀를 모두 블랙으로 바꾼 뒤, 부모를 기준으로 왼쪽으로 회전하여 해결합니다. 이 과정은 결국 엑스트라 블랙을 다른 노드로 옮겨 처리하거나 없애는 것을 목표로 합니다.

**케이스 3: 더블 블랙의 오른쪽 형제가 블랙이고, 그 형제의 왼쪽 자녀가 레드이며, 오른쪽 자녀는 블랙일 때.** 이 경우는 케이스 4와 비슷하지만, 레드가 다른 위치에 있습니다. 해결책은 오른쪽 형제의 왼쪽 자녀를 레드로 만들어서 케이스 4의 형태로 전환한 후, 케이스 4 해결 방식을 적용하는 것입니다. 즉, C와 D의 색깔을 바꾸고 D를 기준으로 오른쪽 회전하여 케이스 4 형태로 만듭니다.

**케이스 2: 더블 블랙의 형제가 블랙이고, 그 형제의 두 자녀 모두 블랙일 때.** 이 경우, 더블 블랙과 형제의 블랙을 모아서 부모에게 엑스트라 블랙 형태로 전달합니다. 이렇게 하면 부모 노드에 엑스트라 블랙이 생기고, 부모의 색깔이 레드였다면 레드 앤 블랙으로, 블랙이었다면 더블 블랙으로 변합니다. 이 부모 노드의 엑스트라 블랙을 다시 해결하는 방식으로 문제를 해결합니다.

**케이스 1: 더블 블랙의 형제가 레드일 때.** 이 경우는 다른 케이스들과 달리 형제가 레드입니다. 해결책은 더블 블랙의 형제를 블랙으로 만든 후, 케이스 2, 3, 4 중 하나로 전환하여 해결하는 것입니다. 이를 위해 부모와 형제의 색깔을 바꿔준 뒤, 부모를 기준으로 왼쪽으로 회전시켜 더블 블랙의 형제를 블랙으로 만듭니다.

다양한 삭제 시나리오를 통해 위에서 설명한 원칙들이 어떻게 적용되는지 살펴보겠습니다. 예를 들어, **15(블랙)를 삭제하면 닐 노드에 엑스트라 블랙이 부여되어 케이스 4 상황이 됩니다.** 이를 해결하기 위해 색깔 변경과 회전 과정을 거쳐 트리의 균형을 재조정합니다.

**33(블랙)을 삭제할 경우에도 닐 노드에 엑스트라 블랙이 부여되며, 이는 케이스 3에 해당합니다.** 케이스 4로 전환하기 위한 색깔 변경 및 회전 후, 다시 케이스 4 해결 방식을 적용하여 균형을 맞춥니다.

**37(레드)처럼 레드 노드를 삭제하면 어떠한 속성 위반도 발생하지 않아 단순히 노드만 삭제하고 상황이 종료**됩니다.

**35(블랙)를 삭제하면 석세서인 40(블랙)의 자리를 대체하는 45(레드)에 엑스트라 블랙이 부여되어 레드 앤 블랙이 됩니다.** 이는 단순한 색깔 변경(블랙으로)으로 해결됩니다.

**40(블랙)을 삭제하면 석세서인 45(블랙)의 자리를 대체하는 닐 노드에 엑스트라 블랙이 부여되어 케이스 2에 해당합니다.** 이를 해결하기 위해 블랙을 부모에게 올려 더블 블랙을 만들고, 이 새로운 더블 블랙 노드가 케이스 4에 해당하므로 다시 색깔 변경 및 회전을 통해 해결합니다.

**50(블랙)을 삭제하면 석세서인 80(블랙)에 엑스트라 블랙이 부여되어 레드 앤 블랙이 되며, 이를 블랙으로 변경하여 해결**합니다.

**80(블랙)을 삭제하면 닐 노드에 엑스트라 블랙이 부여되어 케이스 1에 해당합니다.** 형제의 색깔을 변경하고 회전하여 더블 블랙 형제를 블랙으로 만들고, 이후 케이스 2 방식으로 해결합니다.

**27(블랙)을 삭제하면 석세서인 32(레드)의 레드가 삭제되는 것으로 간주되어 어떠한 속성 위반도 없이 상황이 종료**됩니다.

레드 블랙 트리는 **삽입, 삭제, 검색 모두 최악의 경우에도 빅 O(log N)의 시간 복잡도를 보입니다.** 이는 스스로 균형을 잡는 특성 덕분으로, 일반 이진 탐색 트리가 최악의 경우 빅 O(N)까지 떨어질 수 있는 문제를 개선합니다.

레드 블랙 트리와 AVL 트리의 비교

레드 블랙 트리와 AVL 트리는 모두 이진 탐색 트리이며, **삽입, 삭제, 검색에서 최악의 경우 빅 O(log N)의 시간 복잡도를 가집니다.**

그러나 **삽입/삭제 성능은 레드 블랙 트리가 AVL 트리보다 빠릅니다.** AVL 트리는 균형을 더 엄격하게 유지하므로 삽입/삭제 시 더 많은 균형 조정 비용이 발생하기 때문입니다. 반면, 레드 블랙 트리는 특정 케이스에서 균형 조정이 즉시 종료될 수 있습니다.

**검색 성능은 AVL 트리가 레드 블랙 트리보다 약간 더 빠를 수 있습니다.** AVL 트리가 더 엄격하게 균형을 잡기 때문에 트리의 높이가 더 낮아 검색 경로가 평균적으로 짧아지기 때문입니다.

**균형을 잡는 방식에서 레드 블랙 트리는 트리의 속성을 만족시키며 균형을 잡는 반면**, AVL 트리는 밸런스 팩터(좌우 서브 트리의 높이 차이)가 1을 초과할 경우 균형을 조정합니다.

**응용 사례로는 레드 블랙 트리가 리눅스 커널, 자바의 TreeMap/TreeSet, C++의 map 등** 다양한 곳에 활용되는 반면, AVL 트리는 삽입/삭제가 거의 없고 검색이 주를 이루는 사전(Dictionary)과 같은 상황에 적합합니다. 실제로 레드 블랙 트리가 더 널리 사용되는데, 이는 AVL 트리에 비해 검색 성능 차이가 크지 않으면서 삽입/삭제 성능이 더 우수하기 때문으로 분석됩니다.

레드 블랙 트리에서 노드 삭제 시, '삭제되는 색'이 정의되는 두 가지 주요 경우와 각 경우에 해당 색이 결정되는 방식은 무엇인가요?

레드 블랙 트리 삭제 후, 삭제되는 색이 블랙일 때 위반될 수 있는 속성(2번, 4번, 5번)들을 설명하고, 특히 5번 속성 위반 시 '엑스트라 블랙'을 부여하는 이유와 '더블 블랙', '레드 앤 블랙'의 개념을 설명해주세요.

더블 블랙(블랙 노드에 엑스트라 블랙이 부여된 경우) 문제를 해결하는 네 가지 케이스를 분류하는 기준은 무엇이며, 각 케이스가 어떤 상황을 의미하는지 간략하게 설명해주세요.

레드 블랙 트리의 시간 복잡도는 AVL 트리의 시간 복잡도와 비교했을 때 삽입/삭제 및 검색 성능에서 어떤 차이가 있으며, 이러한 차이가 발생하는 근본적인 이유는 무엇인가요?

레드 블랙 트리가 리눅스 커널이나 Java, C++의 맵 구현 등에서 널리 사용되는 반면, AVL 트리는 주로 검색이 잦고 삽입/삭제가 드문 시나리오(예: 사전)에서 사용되는 이유는 무엇인가요?

레드 블랙 트리 삭제 동작 방식 소개

레드 블랙 트리에서 값 삭제 시 동작 방식 이해

레드 블랙 트리 시간 복잡도와 AVL 트리와의 차이 이해

삭제 전 레드 블랙 트리 속성 만족 상태 확인

일반 바이너리 서치 트리와 동일한 삭제 방식 적용

레드 블랙 트리 속성 위반 여부 확인 및 재조정

레드 블랙 트리 속성 위반 여부 확인 방법

노드 삭제/삽입 상황과 삭제되는 색 확인 중요성 강조

삭제되는 색에 따른 레드 블랙 트리 위반 여부 판단

삭제되는 색의 개념 설명 (자녀 개수에 따른 차이)

자녀가 둘일 경우 삭제된 색은 회색임을 설명

삭제되는 색을 통한 속성 위반 여부 확인 방법 요약

어떤 속성도 위반하지 않음 (5가지 속성 설명)

2, 4, 5번 속성 위반 가능성과 예시 설명

삭제된 노드 색이 레드이면 속성 위반 없음

삭제된 노드 색이 블랙이면 2, 4, 5번 속성 위반 가능성 있음

레드 블랙 트리 속성 위반 시 재조정 방법

블랙 삭제 시 재조정 필요성 강조

루트 노드 블랙으로 변경을 통한 2번 속성 위반 해결

블랙 삭제 시 5번 속성 위반의 당연성 설명

5번 속성 위반 시 추가적인 블랙(엑스트라 블랙) 부여

엑스트라 블랙 처리 및 W 블랙, 레드-블랙 해결

W 블랙과 레드-블랙 해결 방법의 핵심 문제 제기

레드-블랙 해결 방법 (블랙으로 변경)

W 블랙에서 엑스트라 블랙 제거 방법 (4가지 케이스)

삭제된 색이 블랙이고 속성 위반 시 해결 방법 요약

레드 블랙 트리 시간 복잡도 및 AVL 트리와의 비교

레드 블랙 트리 시간 복잡도: O(log n)

레드 블랙 트리와 AVL 트리 비교 (시간 복잡도, 성능 차이)

레드 블랙 트리와 AVL 트리 균형 잡는 방식 차이

레드 블랙 트리와 AVL 트리 응용 사례 비교

(2부) 레드블랙트리(red-black tree)의 삭제는 어떻게 동작할까요? 시간 복잡도는 어떻게 될까요? AVL 트리와 차이는 무엇일까요? 이 영상으로 후련하게 해결하세요 :)

스크립트