편향 이진탐색트리를 해결하기 위한 방법(2) RED-BLACK TREE

이전에 포스팅 했던 편향 이진 탐색 트리를 해결 하기 위한 방법 중 하나인 AVL TREE 가 아닌 또 다른 해결 방법인 RED-BLACK TREE에 대해서 알아보자.

RED-BLACK TREE

레드-블랙 트리도 처음 공부할 때, 많이 헷갈릴 수 있다. 특히 나중에 해결하기 위한 방법으로 Recoloring 과 Restructuring 방식 두 가지가 나오는데, 언제 적용해야 하는지가 분명하지만 이상하게도 자주 헷갈린다! 이를 쉽게 구분하기 위한 개인적인 팁도 제공해보려고 한다.

먼저 RED-BLACK TREE 의 특징에 대해서 알아보자.

RED-BLACK TREE 특징

1. 모든 노드는 빨간색 or 검은색 이다.
2. 루트 노드는 무조건 검은색이다.
3. RED-BLACK 트리에 존재하는 NIL은 검은색이다.
4. 빨간색 자식의 노드는 검정색이다. (즉, 연속으로 빨간색이 나올 수 없다는 것이다.)
5. 모든 리프노드에서 루트노드까지의 Black Depth는 동일하다. (즉, 리프노드부터 루트노드까지의 검은색 노드의 개수가 동일하다.)

RED-BLACK TREE 구성

여기서 제일 이해가 안되는 부분은 아마 저 NIL 일 것이다. 여러 개의 포스팅을 살펴보면 NULL Leaf Node 라고 하는 곳이 좀 많이 보였다. 그럼 NIL이 결국 어떤 약어인건가? 싶어서 여러 방면으로 찾아봤는데 알고보니 NIL은 약어가 아니고 그저 RED-BLACK TREE에서 사용하는 고유 명사이다. 

NIL 이란?

NIL은 위에 사진에서 보이는 것처럼 이진 탐색 트리에서 모든 노드는 자식 노드를 가지고 있어야 한다는 것을 보장하기 위해서 사용하는 것이다. 실제로 구현할 때 NIL은 구현을 하고 NULL; 을 넣거나 혹은 new Object() 를 통해 기본 객체로 지정하여 NIL을 사용 할 수 있다. 

NIL이 필요한 이유는 아래서 나타 날 RED-BLACK TREE의 해결 과정에서 필요하기 때문이다.

 

RED-BLACK TREE 동작 방식

RED-BLACK TREE를 사용할 때, 새 노드의 삽입은 항상 빨간색임이 전제이다.

따라서, 부모 노드가 빨간색이 경우에 삽입을 하게 되면 우리가 위에서 얘기한 RED-BLACK TREE 특징 4번인 빨간색 자식의 노드는 검정색이다. 라는 특징에 위배된다.

 

이러한 문제를 Double-Red 문제라고 한다. 

Double-Red 문제를 해결하기 위해서 기본적인 용어를 정리하고 넘어가는 것이 좋다.

1. 조상노드 G (Grand Parent) : 부모 노드의 부모 노드
2. 부모노드 P (Parent) : 부모 노드
3. 삼촌 노드 U (Uncle) : 부모 노드의 형제
4. 새 노드 N (New) : 삽입되는 노드

Double-Red 문제 해결 방안

Double-Red 문제의 해결 방안은 삼촌 노드가 어떤 색이냐에 따라서 다르게 동작한다.

삼촌 노드가 만약 검정색이라면 Restructuring, 빨간색이라면 Recoloring이 발생한다.

나는 공부하면서 자꾸 이 부분이 헷갈리는 문제가 있었다. 따라서 용어에 대해서 약간 포인트를 주어 외웠는데, 이러한 생각을 했다.

검은색 보다는 빨간색이 좀 더 색깔이 있으니까? 색깔있는 빨간색 -> 색있는거! Recoloring 

삼촌 노드가 빨간색 일 때, Recoloring인 결국 검은색 일 땐 그 반대인 Restructuring 일 것이다.

그럼 Restructuring 이 어떻게 동작하는지 부터 살펴보고 이후에 Recoloring을 살펴보자. 

Restructuring

Restructuring의 동작방식은 다음과 같다.

1. 새 노드 N, 부모 노드 P, 조상 노드 G를 오름차순으로 정렬한다.
2. 셋 중 중간 값을 부모로 하고, 나머지 둘을 자식노드로 설정한다.
3. 새로 부모가 된 노드를 검은색으로 칠하고, 자식 노드들을 빨간색으로 칠한다.
4. 이 때, 기존의 삼촌 노드는 그대로 해당 조상 노드의 자식으로 이어진 상태로 간다.

Restructuring 동작 방식

 

Restructuring을 수행 후에는 Double-Red 문제가 반복적으로 발생하지 않습니다. 즉, 다른 서브트리에도 영향을 미치지 않는다는 것이지요. 따라서, RED-BLACK Tree에서 Restructuring의 시간복잡도는 삽입 시간으로 인한 $ O(logN) $ 밖에 걸리지 않습니다.

하지만 이렇게 이야기 하는 이유가 있겠지요? 바로, 이어서 배울 Recoloring 방식에서는 Recoloring을 수행하더라도, 또 다시 Double-Red 문제가 발생할 수 있습니다. 

여기서 포인트는 무조건 발생한다는 것이 아니고, 발생 할 수도 있다는 것입니다.

Recoloring

Recoloring의 동작방식은 다음과 같습니다.

1. 부모 노드 P와 삼촌노드 U를 검은색으로 변경하고 조상노드 G는 빨간색으로 변경한다.
   1. 조상노드가 루트 노드라면 검은색으로 변경한다.
   2. 조상노드를 빨간색으로 바꿨는데, 다시 Double-Red 가 발생하면 다시 Restructuring, Recoloring 을 수행한다.

Recoloring 동작 방식

이 부분이 은근 많이 헷갈릴 수 있는 부분이라고 생각한다. Restructuring은 새 노드를 사용해서 뭔가 건들였는데, 아마 Recoloring 에서는 새 노드에 대해서는 별로 신경쓰지 않고, 기존에 존재하던 서브트리에 대해 작업을 수행하는 것이라 어색해서 그럴 것이다.

즉, Recoloring은 문제가 발생 했을 때, 새로운 노드를 포함한 조상 노드의 서브 트리에 대해서만 작업을 진행해주면 되는것이다. 

이 때도, 조상 노드는 빨간색으로 바꾼다. 라는 것만 기억을 해도 그 자식 노드는 검은색으로 색칠해야겠구나. 라는 생각으로 편하게 접근하고 기억 할 수 있을 것이다.

 

한 가지 예시 문제를 보여드릴건데, 이 포스팅을 보는 분들이 이해하고자 한다면 동일한 문제를 같이 풀어보고 답을 비교해보는 것이 좋은 방식 이라고 생각합니다.

문제 

Red-Black Tree에서 8, 7, 9, 3, 6, 4, 5 순서로 삽입되는 경우를 그려보시오.

Red-Black Tree 문제 해결 답안

이 부분에서 특히 이해가 안될 수 있는 부분은 7번 과정 부분에서 많은 고민을 했을 것이라고 생각한다.

우리는 기존에 Red-Black Tree의 특징 중 NIL이 존재한다는 것과 NIL 은 항상 검은색이라는 특징이 있다고 위에서 배웠다.

따라서, 해당 답에도 나와있지 않지만, 사실 자식 노드들이 포화 상태로 존재하지 않는 부모 노드에 대해서는 모두 NIL 이 존재 하는 상태라는 것을 이해하는 것이 중요하다. 

p.s

Red-Black Tree를 이해하는데 있어서는 직접 데이터를 넣어보고, 어떤 과정이 이루어지는지 직접 그려보는 것이 가장 이해하기도 편할 것이다. 학부 시절에는 해당 트리를 공부하는데 어쩜 그렇게 이해가 안갔는지, 아마 기존의 이진 트리와 이진 탐색 트리에 대한 구분을 제대로 않고 사용하던 문제 때문이지 않을까 하고 생각을 한다

 

참고로 Red-Black Tree는 자바 개발자들에게 있어서는 꼭 알고 넘어가는 것이 좋다고 생각한다.

자바에서 HashMap, HashSet 등 Hash Table(컬렉션이 아닌 버킷이 담겨있는 그 자료구조 자체)을 사용하는 컬렉션들은 Hash Collision을 해결하는 과정에서 Separate Chaning 방식을 사용하는데, 자바의 JDK1.9 이후로는 일정 사이즈를 넘어서게 되면 리스트 방식이 아닌 Tree 방식을 택하는데, 이때 Tree 방식을 해결하는 과정에 있어서 Red-Black Tree 를 사용해서 해결하기 때문이다.