레드-블랙트리의 삭제

Intro

• 설명이 어려운 내용.
• 비유를 통해서도 암기를 돕기 어려움.
• 케이스가 너무 많아서 감을 잡는것이 목표

레드-블랙트리의 삭제방법(큰그림)

1. BST에서 삭제하듯이 우선 삭제한다.

• 지우려는 값을 가진 노드를 찾음
  
• 교환할 NIL이 아닌 노드 M을 찾음
  
• 값을 복사해옴(색은 복사안함)
  
• M을 지움
  

2. 레드-블랙 트리의 특성이 망가진 걸 고치려 열심히 노력한다..

자식 경우의 수는 생각보다 간단

• M은 언제나 오른쪽(혹은 왼쪽) 하위트리의 최솟값
• M의 왼쪽에 다른 값이 있을 수 없음
  • BST의 삭제 방법 때문
  • M이 최소값이란 말은 곧 M보다 작은 값이 없다는 것인데 M의 왼쪽노드에 값이 있다는것은 곧 M보다 작은값이 존재한다는것이니 말이 안됨
• 결국 아래 경위의 자식을 가진 노드를 지우는 문제
  • 자식이 모두 NIL
  • 자식 중 하나만 NIL

삭제문제 1

문제

결과

문제1번의 경우 BST의 삭제와 동일함 아무 문제가 없음.

삭제문제 2

문제

결과

삭제문제 3

문제

결과

문제 1~3의 공통점

• M이 모두 레드였다.
• 따라서 지워도 아무것도 망가지지 않는다.

M 과 C가 모두 블랙일 경우에만 문제가 복잡해진다.

Why?

• M이 레드면 C는 반드시 블랙
• M이 블랙이고 C가 레드인 경우는?
  
• C의 한쪽자식은 무조건 NIL(BST 삽입규칙에 따라)
  
• C의 다른쪽 자식이 레드일 수는 없다.(C가 레드니까!)
• 그래서 레드 노드의 자식은 모두 블랙이 된다!!
  
• C의 다른쪽 자식이 NIL이 아닌 블랙일 수도 없다. NIL이 아닌 블랙이 와버리면 레드-블랙트리의 균형이 깨지기 때문(어떤 노드와 리프 사이에 있는 블랙 노드수는 동일하다)
  
• 따라서 C의 자식은 무조건 NIL!!