-
레드 블랙 트리를 재정렬해야 하는 경우
자식 노드를 x, 부모 노드를 p, 형제 노드를 s, 형제의 왼쪽 자식을 l, 형제의 오른쪽 자식을 r이라고 할 때 다음과 같은 경우들이 존재한다.
- p가 레드, s는 블랙인 경우 <l의 색상, r의 색상>
- Case 1-1 <블랙, 블랙>
- Case 1-2 <레드 또는 블랙(*), 레드>
- Case 1-3 <레드, 블랙>
- p가 블랙 <s의 색상, l의 색상, r의 색상>
- Case 2-1 <블랙, 블랙, 블랙>
- Case 2-2 <블랙, 레드 또는 블랙(*), 레드>
- Case 2-3 <블랙, 레드, 블랙>
- Case 2-4 <레드, 블랙, 블랙>
※ Case 1-2와 Case 2-2 그리고 Case 1-3과 Case 2-3은 p의 색상이 처리 방법에 영향을 미치지 않으므로 통합한다.
쉽게 배우는 알고리즘 레드 블랙 트리 그림 5-15 각각의 경우에 처리하는 방법은 다음과 같다.
- Case 1-1 p와 s의 색상을 맞바꾼다.
- Case *-2 p를 중심으로 왼쪽으로 회전시키고, p와 s의 색상을 바꾼 다음 r의 색상을 레드에서 블랙으로 바꾼다.
- Case *-3 s를 중심으로 오른쪽으로 회전시키고 l과 s의 색상을 맞바꾼다. 이후 Case *-2를 진행한다.
- Case 2-1 s의 색상을 블랙에서 레드로 바꾼다. 이때 p에 대해서 문제가 발생하므로 p를 문제 노드로 하여 처리를 진행한다.
- Case 2-4 p를 중심으로 왼쪽으로 회전시키고 p와 s의 색상을 맞바꾼다. 문제 발생 노드인 x의 부모가 바뀌게 되므로 노드의 색상에 따라 Case 1-x를 진행한다.
쉽게 배우는 알고리즘 레드 블랙 트리 그림 5-16 - p가 레드, s는 블랙인 경우 <l의 색상, r의 색상>