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

레드블랙트리

이진탐색트리의 불균형한 성장은 검색효율이 최악의 경우 O(n) 이 발생한다. 이러한 불균형을 해결하기 위한 방법은 스스로 규형을 복원하는 것이다. 

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

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

2. 루트노드는 검은색이다. (루트노드 =가장 상위노드)

3. 리프노드는 검은색 (리프노드 =자식노드가 없는 노드)

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

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

NIL 노드는 아무 데이터도 가지고 있지 않는 더미노드이고 NIL노드의 색깔은 검은색으로 취급한다.

 

레드 블랙트리의 회전

레드블랙트리가 균형을 회복하기위한 연산과정 중 회전을 한다 회전은 좌회전, 우회전이 있다.

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

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

레드 블랙트리의 삽입

레드블랙트리의 삽입은 이진탐색트리의 삽입과 같다. 하지만 레드블랙트리는 규칙이 존재하기 때문에 추가 작업을 진행해주어야 한다.

먼저 레드블랙트리에 노드가 삽입되면 이 노드는 빨간색이다. 그리고 양쪽 자식으로 NIL노드를 연결한다. 그리고 어떤 규칙이 위반되었는지 살펴본다.

#1 모든 노드는 빨간색 아니면 검은색이다  

->  O

#2 루트노드는 검은색이다. (루트노드 =가장 상위노드)

-> 루트노드가 빨간색인 경우 다시 검은색으로 바꾼다.

#3 리프노드는 검은색 (리프노드 =자식노드가 없는 노드)

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

#4 빨간 노드의 자식들은 모드 검은색, 하지만 검은색 노드의 자식은 빨간색일 필요는 없다.

-> 규칙에 위배

#5 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일

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

4번 규칙에 위배되는 경우 크게 3가지 경우로 나누어서 처리한다. 이는 부모노드가 조부 노드의 왼쪽 자식일 경우이므로 부모노드가 조부 노드의 오른쪽 자식이었을 경우는 이 반대로 작업을 진행하면 된다.

 

1. 삼촌 노드가  RED인 경우

-> 부모노드와 삼촌노드를 검은색으로 칠하고, 조부노드를 빨간색으로 칠한다. 이 과정에서 조부노드를 RED로 만들었기 때문에 , 그 위로 다시 규칙이 위반되는 게 없는지 루트노드에 도달할 때까지 재귀적으로 살펴보아야 한다.

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

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

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

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

 

##### 레드블랙트리의 구현을 목표로 코딩해보자#######