-
레드 블랙 트리에서의 삽입
레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행한다. 이때, 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 다음과 같이 경우를 나눠 진행을 하게 된다.
- p가 블랙인 경우 삽입 연산을 종료한다.
- s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다.
- s가 블랙인 경우 삽입된 위치에 따른 추가 연산을 진행한다.
- x가 p의 오른쪽 자식인 경우(Case 2.1) p를 중심으로 왼쪽으로 회전한 뒤 Case 2.2를 진행한다.
- x가 p의 왼쪽 자식인 경우(Case 2.1) p²을 중심으로 오른쪽으로 회전하고 p와 p²의 색을 서로 바꾼다.
쉽게 배우는 알고리즘 레드 블랙 트리 그림 5-11