레드블랙트리(자가균형 이진탐색트리)

레드블랙트리 

이진탐색트리의 불균형한 성장은 검색효율을 심각하게 떨어뜨린다. 

이러한 불균형을 해결하기위한 방법은 스스로 균형을 복원하는 것이다.

레드블랙트리는 이러한 불균형을 스스로 복원하는 자가 균형 이진탐색트리이다.

레드블랙트리의 균형 복원 규칙

1. 모든 노드는 빨간색 아니면 검은색

2. 루트노드는 검은색

3. 리프노드는 검은색

4. 빨간 노드의 자식들은 모두 검은색. 하지만 검은색 노드의 자식은 빨간색일 필요 없음

5. 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일(약한 규칙)

NIL 노드는 아무데이터도 가지고 있지 않지만 검은색으로 취급되는 더미노드(Dummy Node)이다.

새로 삽입되는 노드는 리프노드가 되는데, 이때 이 노드의 양쪽 자식으로 NIL 노드를 연결한다.

새로 삽입되는 노드는 무조건 빨간색이기 때문에 루트노드에서 NIL 노드까지 검은색 노드의 수가

 

일정하게 유지된다. 이로서 5번 규칙이 지켜진다.

 

이러한 NIL 노드의 개념은 프로그래밍으로 레드블랙트리를 구현하기 쉽게 하기 위함이다.

 

레드블랙트리의 회전

레드블랙트리가 균형을 회복하기위한 연산과정 중 회전이 발생하는데

회전은 좌회전과 우회전이 있다. 회전규칙은 다음과 같다.

1. 우회전을 할 때에는 왼쪽 자식노드의 오른쪽 자식노드를 부모노드의 왼쪽 자식으로 연결.

2. 좌회전을 할 때에는 오른쪽 자식노드의 왼쪽 자식노드를 부모노드의 오른쪽 자식으로 연결.

 

레드블랙트리의 삽입

기본적으로 레드블랙트리의 삽입은 이진탐색트리의 삽입과 같다.

하지만 레드블랙트리는 삽입 이후에 추가 작업을 진행하는데 이것은 노드의 삽입 과정에서

부서졌을지도 모르는 레드블랙트리의 규칙을 다시 복구하는 작업이다.

 

먼저 레드블랙트리에서 노드가 삽입되면 이 노드는 빨간색이 된다. 그리고 양쪽 자식으로

NIL 노드를 연결한다. 그리고 어떠한 규칙이 위반되었는지 살펴본다.

1. 모든 노드는 빨간색 아니면 검은색

--> 항상 성공

2. 루트노드는 검은색

--> 루트노드가 빨간색인 경우 다시 검은색으로 칠하면 끝

3. 리프노드는 검은색

--> NIL를 연결하기 때문에 문제없음

4. 빨간 노드의 자식들은 모두 검은색. 하지만 검은색 노드의 자식은 빨간색일 필요 없음

--> 문제 발생(규칙 수복 필요)

5. 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일(약한 규칙)

--> 삽입된 리프노드의 양쪽자식으로 NIL 노드를 연결함으로써 지켜지고 있다.

(크리티컬하지 않음)

가장 문제가 되는 것은 4번 규칙으로, 새로 삽입된 노드의 부모역시 빨간색이었다는 것.

이 문제를 해결하기 위해서는 크게 3가지 경우로 나누어서 처리한다.

이는 부모노드가 조부 노드의 왼쪽 자식이었을 경우를 기반으로 설명하는 것이며

부모노드가 조부 노드의 오른쪽 자식이었을 경우는 이 반대로 작업을 진행하면 된다.

1. 삼촌노드가 RED 인 경우

2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우

3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우

1. 삼촌노드가 RED

부모노드와 삼촌노드를 검은색으로 칠하고, 조부노드를 빨간색으로 칠한다.

새로 삽입된 노드는 12 이며 삼촌이 RED	부모노드와 삼촌노드를 검은색으로 칠하고, 조부노드를 빨간색으로 칠한다.

이 과정에서 조부노드를 RED 로 만들었기 때문에, 그 위로 다시 규칙이 위반 되는 게 없는지

 

루트노드에 도달할 때 까지 재귀적으로 살펴보아야 한다.

2. 삼촌노드가 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우

부모노드를 왼쪽으로 회전시켜서 문제를 3번 케이스로 변경한다.

새로 삽입된 노드는 75 이며 삼촌이 BLACK	부모노드(50) 를 왼쪽으로 회전시켜서 문제유형을 3번으로 넘긴다.

3. 삼촌노드가 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우

부모노드를 검은색, 조부노드를 빨간색으로 칠한다. 그 다음 조부노드를 오른쪽으로 회전시킨다.

새로 삽입된 노드는 25 이며 삼촌이 BLACK	부모노드를 검은색, 조부노드를 빨간색으로 칠한다. 그 다음 조부노드를 오른쪽으로 회전시킨다.

- by Raimondo