레드 블랙 트리

균형 이진 탐색 트리를 위해 고안된 자료 구조.
각 노드는 빨간색, 검은색 색상을 나타내는 추가 비트를 저장하며,
삽입, 삭제 중에 균형을 유지하기 위해 사용된다.

레드 블랙 트리 규칙
1. 모든 리프 노드와 루트 노드는 블랙이다.
2. 모든 레드 노드의 자식 노드는 블랙이다.
3. 모든 리프 노드의 Black Dept는 같은 값이다.

레드 블랙 트리 삽입
1. 항상 모든 새로운 삽입은 레드 노드로 삽입한다.

2. 조부모 노드를 G, 부모 노드를 P,
삼촌 노드(조부모 노드 중 부모 노드가 아닌 것)은 U,
새로 삽입된 노드를 N이라고 칭한다.

이 때,
U가 블랙이면 Restructuring을 수행,
U가 레드라면 Recoloring을 수행.

3 - 1. Restructuring은 다음과 과정과 같다.

1. N, P, G를 정렬한다.
2. 가운데 값을 가지는 노드가 최상위 노드(new G)가 된다.
3. 최상위 노드(new G)는 블랙으로,
   최상위 노드를 제외한 나머지 노드(new N, new P)는 레드로 칠한다.

3 - 2. Recoloring은 다음과 과정과 같다.

1. 단순히, P와 U를 블랙으로 칠하고 G를 레드로 칠함.
2. 1번에 의해 레드로 변한 G가 Double Red 문제를 야기시킨다면
   다시 전체 과정의 2번으로 돌아가서 재귀적으로 문제를 해결한다.