> [!date] published: 2023-01-08 얼레벌레 코드짜고 나서야 제대로 정리하는 레드블랙트리 😩 잠이 부족하여 글씨가 엉망인 점... 미안합니다. > 기본적인 (사실 거의 모든) 내용은 아래 유튜브를 기본으로 합니다 (진짜 최고의 강의... ❤️) > > [BJ.31-1 레드블랙트리(red-black tree)의 기본 개념과 특징을 살펴보고, 삽입 때 레드블랙트리가 어떻게 동작하는지를 아주 자세히 설명합니다! - YouTube](https://youtu.be/2MdsebfJOyM) > > [BJ.31-2 레드블랙트리(red-black tree)의 삭제는 어떻게 동작할까요? 시간 복잡도와 AVL 트리와의 차이까지 설명합니다! - YouTube](https://youtu.be/6drLl777k-E) ## 🌟 레드 블랙 트리 각 노드가 최대 2개의 자식들을 가질 수 있는 **이진 트리** 이진 트리 중에서 왼쪽의 서브트리에는 루트의 값보다 작은 값들이, 오른쪽의 서브트리에는 루트의 값보다 큰 값들이 오는 **이진 탐색 트리** 이진 탐색 트리 중에서 "높이" 를 작게 유지하도록 균형을 맞추는 **균형 이진 탐색 트리** 균형 이진 탐색 트리들 중에서 각 노드가 Red 혹은 Black이라는 색깔을 가지고 속성들을 맞추어 나가며 균형을 맞추는 트리가 **레드-블랙 트리**이다. 균형을 맞추는 것이 중요한 이유는 트리의 모든 노드들이 일렬로 쭉 나열되어 있는 형태 같은 worst case의 경우에 탐색 시에 O(n)의 시간 복잡도가 나올 수 있는데, 트리의 균형을 맞추어서 높이를 작게 유지하게 되면 worst case의 경우에도 O(log n)의 시간복잡도를 유지할 수 있기 때문이다. ### ✨ 레드 블랙 트리의 속성 1. 모든 노드는 Red 아니면 Black이다. 2. **루트 노드는 반드시 Black이다.** 3. **nil 노드** (레드 블랙 트리에서 사용하는 개념적인 노드. 존재하지 않음을 의미한다. 레드 블랙 트리의 실질적인 Leaf 노드들은 모두 nil 노드) **는 반드시 Black이다.** 4. **Red 노드의 자식은 반드시 Black이다.** (= Red 노드와 Red 노드가 직접적으로 연결될 수 없다. 연속적으로 존재할 수 없다.) 5. **임의의 노드에서 자신을 루트로 하는 서브트리의 모든 nil 노드까지 가는 경로에서 거치는 Black 노드의 개수는 모두 동일하다.** (자기 자신은 세지 않는다.) (이 때 Black 노드의 개수를 노드 X의 Black height라고 한다.) 삽입 삭제 시에 많이 위반되는 속성들이 4번, 5번 속성이고, 이렇게 위반되는 속성들을 바로잡으면서 레드 블랙 트리의 균형을 맞추어간다. ⭐️ 중요한(?) 사실 하나 : **두 자녀가 같은 색을 가지고 있을 경우에, 부모와 자녀의 색을 바꿔줘도 전체 블랙수 속성 (5번 속성) 은 여전히 만족한다.** ![[127222c5-69fc-44a7-bc23-eb947962e725.png]] ### ✨ Red-Black Tree vs. AVL Tree 참고 : [Red Black Tree vs AVL Tree \| GeeksforGeeks](https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/) Red-Black 트리는 Black 노드를 가지고 높이를 측정하기 때문에 높이에 대한 직접적이고 강력한 규칙은 없지만 AVL 트리는 왼쪽, 오른쪽 하위 트리의 높이의 차이가 2가 넘으면 안된다는 엄격한 규칙이 있다. - Red-Black 트리는 AVL 트리에 비해서 비교적 느슨한 균형을 유지하기 때문에 보다 빠른 삽입과 삭제가 가능하다. (삽입 삭제 시에 균형을 맞추기 위한 연산이 좀 덜 들어감) - AVL 트리는 Red-Black 트리보다 더 엄격한 균형을 이루고 있기 때문에 빠른 검색이 가능하다. - Red-Black 트리는 Map, Set 같은 자료구조의 내부 구현에 주로 사용되고, AVL 트리는 빠른 검색이 필요한 데이터베이스에서 주로 사용된다고 한다. ## 🌟 삽입 > 새로 삽입되는 노드의 색은 무조건 Red이다. 삽입 이후에도 기본적으로는 5번 속성(Black 노드 수 속성)을 맞춰주기 위함이다. > > 삽입 이후 균형을 맞춰주는 과정에서 Root의 색이 바뀔 수 있는데 어차피 Root의 색은 Black으로 바꿔주더라도 다른 속성들에 아무런 영향을 미치지 않기 때문에 모든 작업 뒤에는 아묻따 Root를 다시 Black으로 색칠해주자. 트리의 구조를 바꾸면서도 트리의 특성은 유지하는 방법 ➡️ 회전 ![[9e212534-fe29-4a2f-8b02-a1e63f3584ea.png]] ### ✨ Red 삽입 후 부모가 Red 일 경우 (4번 속성 위반) - CASE 3 **_부모와 자식의 방향이 같음 + 삼촌노드 BLACK_** ![[bcac793e-9fa3-4f83-a05a-bcd89d5f2e24.png]] > ⭐️ 삽입된 **Red 노드**가 부모의 **왼쪽 자식** > > ⭐️ 부모 노드도 Red인데 조부모의 **왼쪽 자식** > > ⭐️ 삼촌 노드는 Black인 경우 (nil 포함) > > 1. **부모와 조부모의 색을 바꾼다.** > 2. **조부모를 기준**으로 **오른쪽 회전** (조부모를 자식으로 내린다.) > 🔁 위 정리의 방향 반전 버전 (저는 바보라서 이것도 정리해야 안 헷갈립니다..) > > ⭐️ 삽입된 **Red 노드**가 부모의 **오른쪽 자식** > > ⭐️ 부모 노드도 Red인데 조부모의 **오른쪽 자식** > > ⭐️ 삼촌 노드는 Black인 경우 (nil 포함) > > 1. **부모와 조부모의 색을 바꾼다.** > 2. **조부모를 기준**으로 **왼쪽 회전** ### ✨ Red 삽입 후 부모가 Red 일 경우 (4번 속성 위반) - CASE 2 **_부모와 자식의 방향이 다름 + 삼촌노드 BLACK_** ![[90adbee7-5eac-4d26-8d4f-16b0a2c7802f.png]] case 2는 이런 형태를 띄는데, new node부터 조부모 노드까지의 경로가 꺾였다는 점만 case 3과 다르다. ➡️ **꺾인 부분을 펴 주면 case 3과 동일하게 해결 가능하다!** ![[2ca3f8bb-20d5-4aa4-bab3-e45224e0093e.png]] > ⭐️ 삽입된 Red 노드가 부모의 **오른쪽 자식** > > ⭐️ 부모 노드도 Red인데 조부모의 **왼쪽 자식** > > ⭐️ 삼촌 노드는 Black인 경우 (nil 포함) > > 1. 부모를 기준으로 **왼쪽으로 회전** > 2. Case 3과 동일한 방식으로 해결한다. > 🔁 위 정리의 방향 반전 버전 > > ⭐️ 삽입된 Red 노드가 부모의 **왼쪽 자식** > > ⭐️ 부모 노드도 Red인데 조부모의 **오른쪽 자식** > > ⭐️ 삼촌 노드는 Black인 경우 (nil 포함) > > 1. 부모를 기준으로 **오른쪽 회전** > 2. Case 3과 동일한 방식으로 해결한다. ### ✨ Red 삽입 후 부모가 Red 일 경우 (4번 속성 위반) - CASE 1 **_삼촌노드 RED_** ![[3ce3f1e5-aee8-4380-94ca-b7961f27f71b.png]] Red 노드가 한쪽에 몰려있지 않기 때문에 단순히 회전하는 것으로 문제를 해결할 수 없다. ➡️ 색깔만 바꾸는 방식으로 현재 삽입된 노드의 4번 속성을 만족시키고, 조부모 노드 쪽에 속성 확인 의무를 넘긴다. > ⭐️ 부모 노드가 **Red** > > ⭐️ **삼촌 노드도 Red**인 경우 > > 1. (아까의 중요한 사실 적용해서) **부모와 삼촌 형제를 모두 Black으로** 바꾸어주고 > 2. **조부모를 Red로** 바꾼 뒤 (부모 형제들이 Red 였으므로 조부모는 당연히 Black이었음) > 3. **조부모에서부터 다시** 4번 속성 위반 여부를 확인한다. ## 🌟 삭제 삭제 방법은 일반적인 이진트리와 같은 방식으로 삭제한다. 중요한 것은 삭제 이후에 속성 위반 여부를 판단하여, 속성이 위반된 경우에는 재조정해서 속성을 다시 맞춰줘야 한다는 것 ### ✨ 속성 위반 여부 판단하기 - 삭제되는 색 속성 위반 여부는 **삭제되는 색**으로 판단할 수 있다. - 삭제하려는 노드의 자녀가 없거나 하나인 경우 : 삭제되는 색 = 삭제하려는 노드의 색 - 삭제하려는 노드의 자녀가 둘인 경우 : 대체 노드가 삭제하려는 노드의 색을 물려받게 되므로 삭제되는 색 = 대체 노드의 색 > ⭐️ 사라지는 색이 Red라면 레드 블랙 트리의 속성들 중에서 영향을 받는 속성이 없으므로 속성을 위반하지 않는다. > > ⭐️ 사라지는 색이 Black이라면 레드 블랙 트리의 속성들 중 2, 4, 5번 속성의 위반 가능성이 있다. ![[02873335-e835-4da7-b0d0-38afb40f3293.png]] ### ✨ 위반 해결하기 (1) - 2번 속성 : Root 노드 삭제 > ⭐️ 대체 노드를 Black으로 바꾸어준다. ### ✨ 5번 속성 위반 해결 방법 - extra black 삭제되는 색이 Black이고, 5번 속성 위반일 때 ➡️ 삭제될 색의 노드의 위치를 대체할 노드에 extra black을 부여한다. Extra black은 경로에서 black 노드를 셀 때 하나의 black으로 세어준다. ![[dada1007-226a-4cb2-946e-1fe73b4922a8.png]] ![[ab9e93d0-b4d2-4717-936f-360c17f5370e.png]] ![[454376ea-1f11-41e5-8fc8-6acd34a5b46c.png]] extra black을 부여받은 노드는 doubly black이 되거나, red-and-black 둘 중 하나가 된다. ### ✨ 위반 해결하기 (2) - 5번 속성 : red-and-black > ⭐️ red-and-black을 black 으로 바꾸면 해결된다. 당연함. 원래 red 였던 노드에 5번 속성 위반을 해결하기 위해서 black을 추가한 것. black을 추가하는 행위는 1, 2, 3, 4번 속성에 영향이 없으므로 그냥 그대로 추가해주면 해결된다 ^\_^ 플러스로 중간에 있던 Black을 삭제하면서 함께 발생할 수 있었던 4번 속성 (Red의 자손으로 Red가 오면 안된다.) 위반도 red-and-black을 그냥 black으로 바꾸어주면서 자연스럽게 해결됨. ~~다른것도 이렇게 간단하면 참 좋을텐데~~ ### ✨ 위반 해결하기 (3) - 5번 속성 : doubly black (CASE 4) > ⭐️ 4가지 case 분류 기준은 doubly black의 형제의 색과 형제의 자녀들의 색 **_Doubly black의 형제가 black + 형제의 같은 방향 자녀가 red인 경우_** Doubly black의 오른쪽 형제가 black이고, 그 형제의 오른쪽 자식이 red일 경우 ![[edcd9709-4dd8-4fdb-84eb-afcb2b2d67db.png]] 결론 도출까지의 흐름을 정리하면 아래와 같다. ![[46f2dbb4-771f-4a58-aa98-4c316ac7327f.png]] 결과만 보면 간단히(😩) 정리할 수 있다. > ⭐️ doubly black의 **오른쪽 형제가 black**이고 > > ⭐️ **그 형제의 오른쪽 자녀가 red**인 경우 > > 1. black인 **오른쪽 형제의 색을 부모의 색으로** 바꿔줌 > 2. red인 **오른쪽 형제의 오른쪽 자녀의 색을 black으로** 바꿔줌 > 3. **부모의 색은 무조건 Black으로** 바꿔준 뒤에 (위 예시에서 B의 역할, 결과적으로 red-and-black이 되어 black이 된다.) > 4. **부모를 기준으로 좌회전**한다. > 🔁 (방향 반전 버전) > > ⭐️ doubly black의 **왼쪽 형제가 black**이고 > > ⭐️ **그 형제의 왼쪽 자녀가 red**인 경우 > > 1. black인 **왼쪽 형제의 색을 부모의 색으로** 바꿔줌 > 2. red인 **왼쪽 형제의 왼쪽 자녀의 색을 black으로** 바꿔줌 > 3. **부모의 색은 무조건 Black으로** 바꿔준 뒤에 (위 예시에서 B의 역할, 결과적으로 red-and-black이 되어 black이 된다.) > 4. **부모를 기준으로 우회전**한다. ### ✨ 위반 해결하기 (4) - 5번 속성 : doubly black (CASE 3) **_Doubly black의 형제가 black + 형제의 같은 방향 자녀가 black, 다른 방향 자녀가 red인 경우_** Doubly black의 오른쪽 형제가 black, 그 형제의 왼쪽 자녀가 red, 그 형제의 오른쪽 자녀는 black ![[93a1f758-e04e-4c95-b6bb-fd4a6435ab3a.png]] 아이디어는 Case 4와 비슷하게 doubly black의 오른쪽 자녀에 red가 오도록 하고, Case 4를 적용해서 해결하는 것이다. ![[3a2ff4ef-c15a-4a1a-a198-4563cb6cc0d0.png]] > ⭐️ doubly black의 오른쪽 형제가 black > > ⭐️ 오른쪽 형제의 왼쪽 자녀가 red > > ⭐️ 오른쪽 형제의 오른쪽 자녀가 black > > 1. 오른쪽 형제의 왼쪽 자녀와 오른쪽 형제의 색깔을 바꾼다. > 2. 오른쪽 형제 기준 우회전 → doubly black의 오른쪽 형제의 오른쪽 자녀 자리에 red가 오게 만든다. > 3. 2번까지의 결과가 case 4의 조건과 동일하므로 이후로는 case4를 적용하여 해결한다. > 🔁 (방향 반전 버전) > > ⭐️ doubly black의 왼쪽 형제가 black > > ⭐️ 왼쪽 형제의 오른쪽 자녀가 red > > ⭐️ 왼쪽 형제의 왼쪽 자녀가 black > > 4. 왼쪽 형제의 오른쪽 자녀와 왼쪽 형제의 색깔을 바꾼다. > 5. 왼쪽 형제 기준 좌회전 → doubly black의 왼쪽 형제의 왼쪽 자녀 자리에 red가 오게 만든다. > 6. 2번까지의 결과가 case 4의 조건과 동일하므로 이후로는 case 4를 적용하여 해결한다. ### ✨ 위반 해결하기 (5) - 5번 속성 : doubly black (CASE 2) **_Doubly black의 형제가 black + 형제의 자녀들이 모두 black인 경우_** ![[f8f50911-a5b9-44c0-afc3-013d7bd510a5.png]] ⭐️ extra black을 받은 부모가 취할 수 있는 조치 - 만약에 부모가 red여서 red-and-black이 된 경우 ➡️ black으로 바꾸고 상황 종료 - 만약에 부모가 root였다면 ➡️ black으로 바꾸고 상황 종료 - 그 외에는 (부모의 부모가 있을테니) case1, 2, 3, 4 중 하나로 해결하면 된다. > ⭐️ doubly black의 형제가 black > > ⭐️ 형제의 두 자녀가 모두 black > > 1. Doubly black 형제 둘의 black을 모아서 그 부모에게 전달 (doubly black은 black, 형제는 red가 된다.) > 2. Extra black을 받은 부모가 알아서 처리한다. ### ✨ 위반 해결하기 (6) - 5번 속성 : doubly black (CASE 1) **_Doubly black의 형제가 red인 경우_** ![[2227c62d-3c89-41de-9652-b853ab1503b8.png]] > ⭐️ Doubly Black의 오른쪽 형제가 red인 경우 > > 1. 부모와 오른쪽 형제의 색을 바꾸고 > 2. 부모를 기준으로 왼쪽으로 회전 > 3. Doubly black 기준 새로운 형제의 색으로 case를 판단하여 처리한다. > 🔁 (방향 반전 버전) > > ⭐️ Doubly Black의 왼쪽 형제가 red인 경우 > > 4. 부모와 왼쪽 형제의 색을 바꾸고 > 5. 부모를 기준으로 오른쪽으로 회전 > 6. Doubly black 기준 새로운 형제의 색으로 case를 판단하여 처리한다. ### ✨ 삭제 결과 처리 방법 정리 삭제 후 속성 위반 여부는 삭제되는 색을 통해서 판단할 수 있다 - 삭제 할 노드에 **자식이 없거나 하나**인 경우 : 삭제되는 색은 **삭제 할 노드의 색** - 삭제 할 노드에 **자식이 둘**인경우 : 삭제되는 색은 **대체 노드의 색** --- - 삭제되는 색이 Red인 경우에는 규정을 위반하지 않으므로 삭제하고 상황 종료 🎉 - 삭제되는 색이 Black인 경우에는 경우에 따라서 2, 4, 5번 속성을 위반할 수 있다. 삭제되는 색을 갖는 노드에 extra black을 부여하고 case를 나누어 정리한다. - 대체 노드가 **root인 경우** → black으로 바꾸어주고 상황 종료 🎉 - 대체 노드의 색이 red여서 **red-and-black**이 된 경우 → black으로 바꾸어주고 상황 종료 🎉 - 대체 노드의 색이 black이어서 **doubly black**이 된 경우 → case 1, 2, 3, 4를 판단하여 상황에 맞게 처리 - Doubly black의 **형제가 black**, **형제와 같은 방향의 형제 자녀가 red** : case 4 - Doubly black의 **형제가 black**, **형제와 다른 방향의 형제 자녀가 red**, **형제와 같은 방향의 자녀가 black** : case 3 - Doubly black의 **형제가 black**, **형제의 자녀들이 모두 black** : case 2 - doubly black의 **형제가 red** : case 1