인공지능 오목 프로그램을 개발하다가 어떤 알고리즘 글을 읽게 되었다.
읽다보니

이 알고리즘에 사용된 map은 내부적으로 레드 블랙 트리로 구현되었기 때문에 삽입,삭제,검색의 시간복잡도가 모두 O(log N)이다.

라는 글을 읽게 되었다. 군대가기전에 들었던 자료구조 수업에서 이진탐색트리를 배운적이 있다. 이진탐색트리는 삽입,삭제,검색의 시간 복잡도가 O(log N)인 자료구조다. 레드 블랙 트리가 대체 뭐길래 내가 열심히 배운 이진탐색트리를 대체하여 사용되는 것인지 공부해보았다.

공부한 주소

레드 블랙 트리

레드 블랙트리는 기존 이진탐색트리의 단점인 최악의 경우 삽입,삭제,검색의 시간 복잡도가 O(log N) 이 아닌 O(N)이 되는 문제를 개선한 자가 균형 이진 트리(self balancing binary tree)이다.

특성

레드블랙트리는 이진탐색트리와 비교했을때 각각의 노드가 black,red색상값을 가진다.
그리고 다음과 같은 룰을 항상 만족시켜야 한다.

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없 으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

검색

레드블랙트리는 기존 이진탐색트리의 검색방법과 동일한 방법을 사용한다. 왼쪽 자식노드가 부모노드의 key값보다 작고 오른쪽 자식노드가 부모노드의 key값보다 크다는 이진탐색트리의 기본 조건을 만족하기 때문이다.

삽입

레드블랙트리에 노드를 삽입하기 위해서는 기존 이진탐색트리에 노드를 삽입하는 과정에 +추가과정이 필요하다. 바로 노드를 추가하고 해당 노드의 색상속성을 레드로 설정후 레드블랙트리의 특성 5가지에 위배되지 않도록 트리를 조정하는 것이다.
다음은 20->30->40->50->60->70순으로 노드를 삽입하는 과정이다.

삽입과정

1. 20삽입
   
   20레드노드를 삽입하고 결과를 보니 레드블랙트리 특성2를 위배하기에 블랙노드로 바꿔준다.
2. 30삽입
   
   30레드노드를 삽입한다. 레드블랙트리 특성3에 따라서 null값을 가진 블랙노드2개를 30레드노드가 가지고 있지만 표기하지는 않았다.
3. 40삽입
   
   40레드 노드를 삽입한다. 2번 과정에서 30의 오른쪽자식노드로 40레드 노드를 삽입하게 되면 레드블랙트리 특성4를 위배한다(더블레드라고한다). 그렇기에 트리의 구조를 변경해야한다. 변경하기 위해서는 삼촌노드(부모의 형제노드)의 값을 확인해야한다. 부모의 형제노드가 블랙노드이거나 없을때는 트리로테이션작업을 통해 더블레드현상을 해결한다. 40레드노드의 부모노드와 부모의부모노드의 크기를 비교해 중간값을 부모노드로만들고 작은값을 왼쪽자식노드 큰값을 오른쪽자식노드로 한다.이때 부모노드는 블랙노드, 자식노드들은 레드노드로 바꾼다.
4. 50삽입
   
   50레드 노드를 삽입하면 40레드노드의 오른쪽자식노드로 가게되는데, 다시 특성4를 위배하게 된다. 이때는 삼촌노드가 레드노드이기에 트리리컬러링작업을 통해 트리를 조정해준다. 방법은 부모노드와 삼촌노드의 색상을 블랙으로 바꾸고 부모의부모노드의 색상을 레드로 바꾼다. 리컬러링작업은 부모의 부모노드가 레드노드로 바뀌기에 다시 더블레드가 발생할 수 있다. 때문에 재귀적으로 레드블랙트리의 모든 특성을 만족시킬때까지 여러번의 연산을 해준다. 그림의 30노드는 레드색상이었지만 루트노드는 블랙이어야 한다는 특성을 만족시키기 위해 블랙노드가 되었다.
5. 60삽입
   
   40을 삽입했을때와 유사하게 더블레드가 발생하므로 트리로테이션 작업을 통해 레드블랙트리의 특성을 만족하게만든다.
6. 70 삽입
   
   50을 삽입했을때와 유사하게 더블레드가 발생하므로 트리리컬러링작업을 통해 레드블랙트리의 특성을 만족하게 만든다. 여기서 50노드는 루트노드가 아니므로 그대로 레드노드임을 볼 수 있다.

이진탐색트리와의 비교

이 자료는 이진탐색트리에 20->30->40->50->60->70을 차례로 삽입한 시뮬레이션 자료이다. 레드블랙트리에 비해 트리의 좌우가 불균형한 모습을 확인할 수 있다.

시간복잡도

레드 블랙트리는 이진탐색트리와 같이 삽입 시간복잡도가 O(log N)이다. 하지만 차이점은 이진탐색트리는 최악의 경우 시간복잡도가 O(N)이 될수 있다. 하지만 레드블랙 트리는 루트 노드부터 가장 먼 잎노드 경로까지의 거리가, 가장 가까운 잎노드 경로까지의 거리의 두 배 보다 항상 작다. 이런 특성에 의해 트리의 좌우가 비교적 균형을 이루게 되어 최악의 경우에도 시간복잡도 O(logN)이 보장이 된다. 이런 장점이 있기에 이진탐색트리를 대체하여 많이 사용된다.

삭제

(요약: 이진 탐색 트리의 삭제과정을 밟고 레드블랙트리의 특성에 위배되지 않도록 트리모양을 조정해준다.시간 복잡도는 O(logN))
경우의 수가 너무 많으니 다음에 생각날때 정리하기로 한다.