-
레드 블랙 트리에서의 삭제
레드 블랙 트리의 삭제는 기본적으로 이진 검색 트리의 삭제 방법에 따라 삭제한 뒤 색상에 맞게 다시 정렬하는 방식을 사용하게 된다.
자식이 두 개인 경우 오른쪽 자식의 최소 노드의 값과 삭제하려는 노드의 값을 교환한 뒤 최소 노드를 삭제하는 연산을 진행하는데 이때 값의 교환은 레드 블랙 트리의 속성을 바꾸지 않으므로 노드의 색상을 다시 정렬하는 것은 자식이 없거나 하나만 존재하는 경우만 진행한다고 생각해도 된다.
삭제하려는 노드를 m, 자식 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 처할 수 있는 상황은 다음과 같다.
- m이 레드인 경우 삭제 연산을 종료한다.
- m이 블랙이지만 x가 레드인 경우 삭제 연산을 종료한다.
- m이 블랙이고 x도 블랙인 경우 주변 상황에 따라 재정렬해 줘야 한다.
쉽게 배우는 알고리즘 레드 블랙 트리 그림 5-12, 5-13