[WEEK06] RB 트리 Case 정리

---

---

삽입 시 재조정 Case

[Case 1]

• 부모도 RED, 삼촌도 RED
  • 부모와 삼촌을 BLACK으로 바꾸고 할아버지를 RED로 바꾼 후 할아버지에서 다시 확인

[Case 2]

• 삽입된 노드가 부모의 오른쪽 자녀, 부모가 RED이고 할아버지의 왼쪽 자녀, 삼촌은 BLACK
  • 부모를 기준으로 왼쪽으로 회전한 후 Case 3 방식으로 해결
• 삽입된 노드가 부모의 왼쪽 자녀, 부모가 RED이고 할아버지의 오른쪽 자녀, 삼촌은 BLACK
  • 부모를 기준으로 오른쪽으로 회전한 뒤 Case 3의 방식으로 해결

[Case 3]

• 삽입된 노드가 부모의 왼쪽 자녀, 부모가 RED이고 할아버지의 왼쪽 자녀, 삼촌은 BLACK
  • 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽으로 회전
• 삽입된 노드가 부모의 오른쪽 자녀, 부모가 RED이고 할아버지의 오른쪽 자녀, 삼촌은 BLACK
  • 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 왼쪽으로 회전

---

삭제 시 재조정 Case

[Case 1]

• DOUBLY BLACK의 오른쪽 형제가 RED일 때
  • 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤
  • DOUBLY BLACK을 기준으로 Case 2, 3, 4 중 하나로 해결
• DOUBLY BLACK의 왼쪽 형제가 RED일 때
  • 부모와 형제의 색을 바꾸고 부모를 기준으로 오른쪽으로 회전한 뒤
  • DOUBLY BLACK을 기준으로 Case 2, 3, 4 중 하나로 해결

[Case 2]

• DOUBLY BLACK의 형제가 BLACK and 그 형제의 두 자녀가 모두 BLACK일 때
  • DOUBLY BLACK을 BLACK으로, 형제를 RED로 바꾼 후, 부모가 EXTRA BLACK을 해결하도록 위임한다.

[Case 3]

• DOUBLY BLACK의 오른쪽 형제가 BLACK and 그 형제의 왼쪽 자녀가 RED and 오른쪽 자녀가 BLACK일 때
  • 형제와 형제의 왼쪽 자식 색을 바꾸고, 형제를 기준으로 오른쪽으로 회전하면 형제는 RED인 오른쪽 자식을 가진 BLACK이 된다.
  • 이후에는 Case 4를 적용하여 해결
• DOUBLY BLACK의 왼쪽 형제가 BLACK and 그 형제의 오른쪽 자녀가 RED and 왼쪽 자녀가 BLACK일 때
  • 형제와 형제의 오른쪽 자식의 색을 바꾸고, 형제를 기준으로 왼쪽으로 회전하면 형제는 RED인 왼쪽 자식을 가진 BLACK이 된다.
  • 이후에는 Case 4를 적용하여 해결

[Case 4]

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