아침 CS - (4) 레드 블랙 트리

레드벨벳과 이름이 비슷하여(…) 관심을 갖게된 레드 블랙 트리(Red - Black Tree) 는 최근 함수형 프로그래밍의 추세에서 특히 많이 사용되고 있는 트리라고 한다.

이진 트리가 불완전하거나 편향되면 가질 수 있는 여러 문제를 해결해줄 수 있으며 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행시간을 보장한다.

일정한 실행 시간을 보장해야만 하는 다양한 상황에서 유용하게 쓰일 수 있을 것이다.

다섯 가지의 대원칙이 있다.

뭔 소리냐?

레드 블랙 트리에 대해 자세히 알아보기에 앞서 이진 탐색 트리에 대해 먼저 간략히 알아본다.

이진 트리와 다르게 부모 노드보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하는 트리를 이진 탐색 트리라고 한다.

이런 식의 정렬을 수행해 놓으면 단순히 트리를 중위 순회 하는 것만으로도 오름차순 정렬된 값을 얻을 수 있다.

위 트리를 중위 순회(왼쪽 - 부모 - 오른쪽 순으로 방문)하면

1 3 4 6 7 8 10 13 14 순으로 방문하며 값을 빼올 수 있다.

그러나 효율적인 것처럼 보이는 이진 탐색 트리도 편향 트리의 문제를 해결할 순 없다. 즉 루트 노드보다 큰 값이 계속 들어온다면 트리의 오른쪽에만 노드들이 쌓이게 되고, O(n)의 시간으로 탐색할 수밖에 없게 된다.

삼촌 노드란? 삼촌 노드는 부모와 같은 부모를 갖는 다른 노드를 말하는 것이다.

위 예제에서 보자면 4번 노드의 삼촌 노드는 1번일 것이다. 이모 노드라고 해도 좋다. 어쨌든 공식 명칭은 uncle node다.

레드 블랙 트리는 균형 트리 이다. 편향성을 보이지 않는다.

어떻게?

삽입

아래 그림을 보며 이해하려고 노력해보자.

참고 그림

일단, 첫 노드를 블랙으로 삽입한다

(규칙 2, 루트 노드는 블랙이다)

지금부터는 삽입 과정에서 발견될 수 있는 규칙 위반상황, 그리고 레드 블랙 트리가 이 문제를 어떻게 해결하는지에 대해 보겠다.

이런 경우는 부모 노드의 부모 노드, 즉 조부모 노드는 반드시 검은색이여야 한다.

규칙 4. 레드 노드는 연달아 나타날 수 없다 를 위배하게 되기 때문이다.

이 conflict를 해결하기 위해서 할아버지를 빨간 색으로 바꾸고 부모와 삼촌은 검은색으로 바꿔주는 작업을 수행하면 된다. 이를 색 변환 이라고 부른다.

이번에도 2번과 7번 노드가 모두 빨간 노드로 규칙 4가 위배되었다.

아까와 같이 11번과 7번의 색깔을 바꾸는 것만으로는 문제를 해결하기 어렵다. 루트 노드가 빨간 노드일 수 없기 때문이다.

이런 경우 노드 전체를 오른쪽으로 한칸씩 미는 작업을 수행하면 되겠는데 이를 회전 이라고 부른다.

조금 더 간단한 그림으로 다시 알아보자.

회전 참고도

새로 삽입된 노드 X가 부모 A와 같은 붉은색을 갖는 문제가 발생하였다. 이 문제를 해결하기 위해 우회전을 수행하고 트리를 재구조화하면 된다.

솔직히 말해 아직 레드블랙트리에 대한 정확한 이해는 하지 못한 상태이다.

그러나 완벽한 학습 후 정리를 하기 보단 학습을 하며 정리를 조금씩 해 나가고, 오랜만에 이진 탐색 트리의 개념도 다시 살펴보는 게 의미있다 판단하여 아침 CS 주제로 좀 부담스런 주제를 선정해보게 됐다.

이 포스트는 두고두고 조금씩 업데이트할 생각이다.

참고 문헌

CHAPTER 14: RED-BLACK TREES