[Red-Black 트리]삭제

Red-black 트리의 삭제 방식

---

📌삽입 overview

1. 삭제전 RB트리의 속성을 만족한 상태
2. 삭제 방식은 일반적인 BST와 동일
3. 삭제 후 RB트리 속성 위반 여부 확인
4. RB트리 속성을 위반했다면 재조정
5. RB트리 속성을 다시 만족

 💡속성 위반 여부 확인

• RB트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요!

💡삭제되는 색이란?

• 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색=삭제되는 노드의 색(여기선 유요한값을 가지는 자녀를 의미 닐노드는 포함 x)

• 25 삭제 -> red 삭제
• 80 삭제 -> black 삭제
• 40 삭제 -> black 삭제

📌삭제하려는 노드의 자녀가 둘이라면

• 삭제되는 색 = 삭제되는 노드의 successor의 색

👉🏻20 삭제 -> successor 25 -> red 삭제

• why?
•  20의 자녀는 2개, 20을 삭제하게 되면 2진탐색의 삭제 방식과 동일하기 때문에 25가 20을 대체하게 됨 25는 사라지고 20의 위치에 25가 오게됨 이때 삭제되는 색은 20의 red가 아니라 25의 red이다. 왜냐하면 25가 20의 자리를 대체하게 되면서 25는 20의 색을 물려받게 됨 결국 삭제되는 색은 20이 아니라 successor인 25의 색이 삭제가 됩니다.

👉🏻35 삭제 -> successor 25 -> red 삭제

• why?
• 35의 자녀는 2개, 35를 삭제하게 되면 37이 35를 대체하게 됨 그래서 35는 삭제가 되고 35의 자리에 37이 올라오게 됨 37도 그 위치에서 사라지게 되고 35 자리에 올라오게 됨 이때 35의 색은 그대로 유지가 됨 그래서 실제로 삭제되는 색은 37 올라오기전에 그 위치에서 삭제가 됨

 👉🏻50 삭제 -> successor 80 -> red 삭제

• why
• 50의 자녀는 두개, 삭제를 하게 되면 80이  50을 대체하게 됨 그래서 50은 삭제가 되고 50의 색은 80이 물려받게돼서 실제로 삭제되는 색은 black

🖋정리 - 속성 위반 확인 여부는  삭제되는 색을 통해

• 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색은 삭제되는 노드의색
• 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색은 삭제되는 노드의 successor의 색

---

📌Red가 삭제될때 속성 위반 여부 확인

• 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다

📌Black이 삭제될때 속성 위반 여부 확인

• 삭제되는 색이 black 이라면 #2, #4, #5 속성을 위반 할 수 있다.
• #2 : 루트 노드는 blakc
• #4 : 노드가 red라면 자녀들은 black
• #5 : 임의의 노드에서 그 노드의 자손 nil 노드들까지 가는 경로들의 black 수는 같다.

  📌Black이 삭제될때 예시

📌40삭제 

• 40의 black삭제, #4와, #5를 위반한다.
• #4 : 노드가 red라면 자식은 black
• #5 : 임의의 노드에서 그 노드의 자손 nil 노드들까지 가능 경로들의 black수는 같다

📌35삭제

• 35의 black삭제 , #2를 위반한다
• 35는 자녀가 하나
• 35의 black이 삭제됨
• 50이 루트가 되고 #2 속성 위반
• 50을 black으로 바꿔서 해결

 💡삭제되는 색이 black -> 주로 위반하는 속성

• 삭제되는 색이 black일때 특수한 상황을 제외하면 #5속성을 항상 위반하게 된다.
• #5 : 임의의 노드에서 그 노드의 자손 nil노드들까지 가는 경로들의 black수는 같다.

📌삭제되는 색이 black이고 #5위반일 때

• extra black 부여
• #5 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다.

📌extra black의 역할

• 경로에서 black 수를 카운트 할 때 extra black은 하나의 black으로 카운트 된다.

📌black삭제 예시

📌10 삭제

• 10은 자녀가 없음, 삭제되는 색은 black
• black이 삭제됐으므로 #5 속성을 위반했고 extra black을 부여해서 #5속성을 다시 만족 시켜야한다.
• 어디에 extra black을 부여해야할까?
• 삭제된 색의 위치를 대체한 노드 -> 삭제된 색은 10의 black이므로 10의 위치를 대체한 노드인 nil노드에 extra black을 부여!

• 10의 위치를 대체한 nil노드에 extra black을 부여 -> #5속성을 다시 만족
• doubly black : extra black이 부여된 black 노드

📌30 삭제

• 30은 자녀가 하나라서 삭제되는 색은 30의 black
• #5번 속성을 위반하므로 extra black 부여
• 삭제된 색은 30의 black이었으므로 30의 위치를 대체한 노드인 25에 extra black부여

• 30의 위치를 대체한 노드인 25에 extra black부여 -> #5 속성을 다시 만족
• red-and-black : extra black이 부여된 red노드

📌50삭제

• 50은 자녀가 둘이라서 삭제되는 색은 50의 successor인 80의 black

• 80의 위치를 대체한 nil노드에 extra black 부여 -> #5 속성 다시 만족

 🖋정리

• 삭제되는 색이 black이고 #5위반일 때
• extra black 부여 결과
• extra black을 부여받는 노드는 doubly black이 되거나 red-and-black이 된다.

---

📌red and black 해결하기

• red and black을 black으로 바꾸면 해결
• #5번 속성을 만족, #4번 속성을 위반한 상태라면 위반 문제 자연스럽게 해결

📌30삭제

• 30은 자녀가 하나라서 삭제되는 색은 30의  black-> #5 위반
• 20과 25가 바로 연결되면서 #4 위반
• #4 : 노드가 red라면 자녀들은 black
• #5 : 임의의 노드에서 그 노드의 자손 nil 노드들까지 가는 경로의 black 수는 같다.

• 25는 red and black이 됐으니 25를 black으로 바꿔주면 종료

• #4와 #5를 위반한 걳을 동시에 해결, red-black 트리의 모든 속성을 만족

---

📌doubly black 해결하기 (오른쪽 자녀 red)

• extra black을 부여했더니 doubly black 노드가 생겼다면 결국 extra black을 어떻게 없앨것인지가 관건
• doubly black의 extra black을 없애는 방법은 총 네 가지 case로 분류됨
• 네 가지  case로 분류할 때의 기준은 doubly black의 형제의 색과 그 형제의 자녀들의 색

📌📌

• doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red 일때,
• 그 red를 doubly black 위로 옮기고 옮긴 red로 extra black을 전달해서, red and black으로 만들면 red and black으로 바꿔서 해결

💡색을 바꾸면서도 #5 속성 유지하기

• RB 트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5속성은 여전히 만족한다.

•  doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red 일때,
• red를 왼쪽으로 보내기 위해서는 D의 위치가 red가 돼야 하고, 이를 위해 D의 black을 C와 E로 보내고 D를 red로 바꾼다.
• 여전히 #5 속성을 만족하고 있다.

• red가 왼쪽으로 넘어갈 수 있도록 왼쪽으로 회전 전에 B와 D의 색을 바꿔준다.

• B를 기준으로 왼쪽으로 회전한다.

• 회전 후에도 #5속성을 만족한다.
• A와 C의 extra black을 b로 올린다. 그렇게 해도 여전히 #5는 만족한다.

• B는 red and black이 됐기 때문에 b의 색을 black으로 바꿔서 extra black을 제거하면 문제해결

• 최종적인 모습

🖋정리 - extra black 부여 후 doubly black 해결하기

case.4

• doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일때, 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로 바꾼후에 부모를 기준으로 왼쪽으로 회전하면 해결

---

📌doubly black 해결하기 (왼쪽 자녀 red)

• doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red일때, double black의 형제의 오른쪽 자녀가 red가 되게 만들어서 이후엔 case.4를 적용하여 해결

• E의 위치에 red가 오도록 만들기 위해 C와 D의 색을 바꾼 후에 D를 기준으로 오른쪽으로 회전하면 된다.

• 이제 case.4를 적용해서 해결한다. C는 B의 색으로 B와 D는 black으로 바꾼 후 B를 기준으로 왼쪽으로 회전하면 해결 

\

• 최종적으로 이러한 형태가 된다.

🖋정리 - extra black 부여 후 doubly black 해결하기

case.3

• doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red &그 형제의 오른쪽 자녀는 black일 때
• doubly black의 형제의 오른쪽 자녀를 red가 되게 만들어서 이후엔 case.4를 적용하여 해결

---

📌doubly black 해결하기(형제의 자녀가 둘다 black)

• doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다.

• A와 A의 형제인 D의 black을 모아서 부모에게 전달하게 되면 A와 D에서 black을 모았기 때문에 A는 여전히 black이고 D는 red가 된다.

• black을 전달받은 b는 red-and-black 혹은 doubly black이 된다.
• #5 속성은 여전히 만족되고 있다.
• B가 red and black이 됐다면 black으로 바꿔주면 상황은 종료 되지만 B가 doubly black이 됐다면 B가 루트노드라면 black으로 바꿔서 해결
  • 만약 아니라면 case.1 ,2,3,4중에 하나로 해결

🖋정리

case.2

• doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 black을 해결하도록 위임한다. 

---

📌doubly black 해결하기(형제가 red일때)- doubly black의 case.1 상황일 때 해결방법 

• doubly black의 형제를  black으로 만든 후 case 2, 3, 4 중에 하나로 해결
• B를 기준으로 왼쪽으로 회전하면 doubly black A의 형제는 C가 되며 즉, black이 된다.

• 회전 후에도 #5 속성을 만족하려면 왼쪽으로 회전하기 전에 b와 d의 색을 바꿔준다. 

• doubly blackd의 형제가 red일 때 doubly black의 형제는 black 됐으므로 case 2,3,4 중에 해결책을 찾으면 된다.

🖋정리

case.1

• doubly black의 오른쪽 형제가 red일때
• 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽

---

📣배웠던 내용 정리!!!!!!!!

👉🏻#5 위반 해결하기

• 삭제되는 색이 black 일때 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여한다.
• 대체한 노드가 red-and-black 이 됐다면 black으로 바꿔주면 끝
• 대체한 노드가 doubly black이 됐다면 case 1,2,3,4 중에 하나로 해결

---

📌red - black 트리 삭제 예제

 

📌delete(15)

• 삭제되는 노드는 15, 삭제되는 색은 15의 black
• 15의 위치를 대체할 nil node에 extra black을 부여한다.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야한다.
• doubly  black의 왼쪽 형제도 black이고 그 형제의 왼쪽 자녀가 red여서 case.4에 해당한다.

• 5를 부모 노드의 색인 red로 바꾸고 5의 부모인 10과 5의 왼쪽 자녀인 2는 black으로 바꾼뒤 10을 기준으로 회전한다.

• 최종적으로 레드블랙트리의 모든 속성을 만족한다.

📌delete(33)

• 삭제되는 노드는 33, 삭제되는 색은 33의 black
• 33의 위치를 대체할 nil node에 extra black을 부여한다.

• nil 노드는 doubly black이 됐기 떄문에 어떤 case인지 분류해야한다.
• doubly black의 왼쪽 형제가 black이고 그 형제의 왼쪽 자녀는 black이고 오른쪽 자녀가 red여서 case.3에 해당한다. 

• case.4 의 방식으로 해결할 수 있게 case.4의 형태로 먼저 만들려면
• 25와 27의 색을 바꾸고 25를 기준으로 왼쪽으로 회전한다.

• case.4의 형태가 됐으므로 27의 색을 부모인 30의 색으로 바꾸고
• 27의 부모와 왼쪽 자녀는 black으로 바꾼뒤 30을 기준으로 오른쪽 회전을 한다.

• 레드블랙 트리의 모든 속성을 만족한다.

📌delete(37)

• 삭제되는 노드는 37
• 삭제되는 색은 37의 red
• red가 삭제되므로 37 삭제후 상황 종료

📌delete(35)

• 삭제되는 노드는 35
• 삭제되는 색은 40의 black
• 40의 위치를 대체할 45에 extra black을 부여한다.
•  자녀가 2개 이기 때문에 대체할 노드는 35의 석세서 오른쪽 서브트리에서 가장 작은값이기 때문에 40이 35의 석세서가 되고 35가 삭제되면 40이 35의 자리를 대체하게됨 이때 삭제되는 것은 40은 35의 색을 물려받기 때문에 40의 색이 삭제됨
• 그래서 #5 속성 위반

• 45는 red and black이 됐기 때문에 45를 black으로 바꾸면 red-black 트리의 모든 속성을 만족하며 상황종료

📌delete(40)

• 삭제되는 노드는 40, 삭제되는 색은 45의 black
• 45의 위치를 대체할 nil node에 extra black을 부여한다.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야한다.
• doubly black의 형제도 black이고 그 형제의 두 자녀도 black이기 때문에
• case.2에 해당한다.

• nil 노드의 extra black과 80의 black을 모아서 50으로 올리고
• 80은 red로 바꿔준다.
• 50은 extra black을 가진다.

• 50이 doubly black이 됐기 때문에 이번엔 어떤 case인지 분류해야한다.
• doubly black의 왼쪽 형제가 black이고 그 형제의 왼쪽 자녀가 red이기 때문에
• case.4에 해당한다.

• 20을 부모 노드의 색인 black으로 바꾸고 20의 부모인 45와 20의 왼쪽 자녀인 5는 black으로 바꾼뒤
• 45를 기준으로 오른쪽 회전을 한다.

• 모든 속성 만족

📌delete( 50)

• 삭제되는 노드는 50, 삭제되는 색은 50의 black
• 50의 위치를 대체할 80에 extra black을 부여한다.

• 80은 red and black이 됐기 떄문에 80을 black으로 바꾸면
• red - black 트리의 모든 속성을 만족하며 종료

 📌delete(80)

• 삭제되는 노드는 80, 삭제되는 색은 80의 black
• 80의 위치에 대체할 nil노드에 extra black을 부여한다.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야한다.
• doubly black의 형제가 red이기 때문에 case.1에 해당한다.
• case.1 의 형태를 바꿔서
• case.2.3.4 중에 하나의 형태로 만든다. 

• 형제와 부모의 색을 바꾼뒤 45를 기준으로 오른쪽 회전한다. 

• doubly black의 형제가 black이고 형제의 두 자녀가 모두 black이기 때문에 case.2의 방식으로 해결한다.

• 이제 모든 속성 만족

 📌delete(27)

• 삭제되는 노드는 27
• 삭제되는 색은 30의 red
• red가 삭제되므로 27삭제 후 상황종료

• 모든 속성을 만족하기 때문에 상황종료

---

📌red-black 트리의 시간 복잡도

• 레드블랙 트리는 스스로 균형을 잡기 때문에 O(logn)