개념

• 삽입 전 RB트리 속성을 만족한 것을 전제로 한다.
• 삭제 방식은 일반적인 BST와 동일하다.
• 삽입 후 RB트리의 위반 여부를 확인하고, 위반했다면 재조정하여 다시 만족하도록 바꾼다.
  • 이때 삭제되는 색이 중요하다.
    • Red가 삭제되는 경우 위반 요소가 없다.
    • Black이 삭제되는 경우 2번, 4번, 5번의 위반 가능성이 생긴다.
      • 2. 루트 노드는 Black이다.
      • 4. Red의 자녀들은 Black이다.
      • 5. 임의의 노드에서 자손 Nil노드까지 가는 경로들의 Black의 수는 같다.
    • 특히 이중 2번, 4번의 위반 가능성이 크다.
      • 2번 → 루트를 Black으로 변경하여 해결한다.
      • 5번 → 항상 일어난다. → 재조정을 해준다.

재조정

• 위에서 말했 듯, 삭제된 색이 Black인 경우에만 재조정이 일어난다.
• 재조정은 방금 삭제된 노드의 위치로 이동한 노드의 색을 보고 결정한다.
  • 삭제된 위치로 Red가 붙었다면, 검정으로 변경되고 종료된다.
  • 삭제된 위치로 Black이 붙었다면, 재조정이 일어난다.
    • Nil노드도 Black이다.
    • 그래서 Nil노드가 삭제된 위치에 왔다면, Nil노드에 부모를 설정해주어야 Fixup 코드가 동작한다.

삭제방식

전제조건

• 탐색위치는 root가 아니다. 그리고
• 탐색 위치의 색깔은 Black이다.
• 위의 조건을 만족하지 않는다면 반복문을 빠져나온다.

case1

• 조건
  • 형제노드의 색이 Red이다.
  • 삭제 이전, Rb Tree의 조건을 만족했을 것이므로, 부모노드의 색과 형제노드의 자녀의 색은 모두 Black일 것이다.
• 과정
  • 부모 노드와 형제 노드의 색을 바꾼다.
  • 부모 노드를 기준으로 회전을 한다.
  • 형제 노드를 재설정해준다.
• case1을 거친 이후, case2 혹은 case3과 case4로 탐색 위치 에서의 조정을 계속 수행한다.

case2

• 조건
  • case 1을 거쳤으므로, 형제 노드의 색은 Black으로 고정되었다.
    • case1을 수행하지 않았더라도, case1의 조건에 부합하지 않았다면 형제 노드의 색은 Black이다.
  • case 2는 이 상태에서, 형제 노드의 모든 자녀 노드 색이 검정일 때 수행한다.