Red Black Tree

순수한 이진 탐색 트리의 단점은 불균형하며 검색 효율을 심각하게 저하시킨다.

이런 이진 탐색 트리의 단점을 보완한 것이 레드 블랙 트리이다.

 

레드 블랙 트리에서 노드는 트리 전체의 균형을 유지할 수 있게 하는 아주 중요한 비결이다.

 

레드 블랙 트리의 규칙

 

1. 모든 노드는 Red아니면 Black이다.

2. 루트 노드는 검은색이다.

3. 잎 노드는 검은색이다.

4. Red 노드의 자식들은 모두 검은색이다. 하지만 Black 노드의 자식이 Red일 필요는 없다.

5. 루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.

 

레드 블랙 트리의 잎 노드는 모두 NIL로 표시되어 있다.

NIL 노드는 아무 데이터도 가지고 있지 않지만, 색깔만 검은색인 더미 노드이다.

 

왜 아무 데이터도 가지고 있지 않은 NIL노드를 저장 공간을 할애하면서 사용하는 이유는

레드 블랙 트리를 구현하기 쉽게 하기 위해서이기 때문이다.

 

원래의 잎 노드들이 검은색이든 빨간색이든 NIL노드를 양쪽 자식으로 연결해서 NIL노드가

잎 노드가 되면 "모든 잎 노드는 검은색이다."라는 규칙을 유지시킬 수 있기 때문이다.

 

 

레드 블랙 트리의 기본 연산

레드 블랙 트리는 이진 탐색 트리인데,,

레드 블랙 트리에서는 이진 탐색을 그대로 사용하면 된다.

 

하지만 이진 탐색 트리처럼 삽입, 삭제를 하면 레드 블랙 트리에서는 문제점이 발생하게 되는데,

삽입과 삭제 후의 기본 뒤처리가 주된 내용이라고 할 수 있다.

 

 

회전(Rotate)

 

회전은 부모-자식 노드의 위치를 서로 바꾸는 연산이다.

회전은 방향에 따라서 우회전, 좌회전으로 나뉠 수 있다.

 

- 우회전 : 왼쪽 자식과 부모의 위치를 교환

- 좌회전 : 오른쪽 자식과 부모의 위치를 교환

 

하지만 그냥 회전을 시켜버리면 문제가 발생하게 되는데,

이진 탐색 트리의 특성상 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 커야하기 때문이다.

 

모든 조건을 만족시키면서 회전을 할때의 조건

 

- 우회전을 할 때

왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 연결한다.

- 좌회전을 할 때

오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노드의 오른쪽 자식으로 연결한다.