Red-Black Tree - 1

지금까지 개발을 열심히 해오던 놈이 괜찮은 알고리즘 하나 제대로 다룰줄 몰라서 .. 개인적으로 충격!! ㅋㅋ 대학교 다닐때 왠만해선 A,A+ 다 나왔는데.. ㅠㅠ 알고리즘만.. B+.. 흑흑.. 열심히 할껄....;; 쩝 ㅋㅋ 아무튼!

그래서 탐색, 삽입, 삭제 시 나름 괜찮고 간지나는 방법인 레드블랙 트리를 공부해볼까합니다. 뭐 보통 단점하면 이진트리보다 색 정보가 더 필요해서 용량을 더 차지한다고 나왔는데 .. 최상위 비트 잘 활용하면 이진트리랑 용량은 똑같? 일단 공부를 해봐야겠지요.

뭐 책에도 레드블랙트리에 대해 많이 나와있고 인터넷을 찾아봐도 수두룩하니 공부하기는 쉬울 것같네요.

그래도 전 책이 있으니 "뇌를 자극하는 알고리즘" 이라는 책에 나와있는 내용을 토대로 공부를 해보겠습니다. 간간히 이해 안되는 부분은 인터넷도 참고 ㅋ 아무튼 시작해보겠습니다.

==============================================================

레드 블랙 트리

우리 보통 알고 있는 이진트리는 아주 간단한 구조로 되어 있습니다. 루트 노드를 중심으로 왼쪽엔 루트노드보다 작은 노드가 오른쪽엔 루트노트보다 큰 노드가 들어가게 됩니다. 이러한 이진 트리는 크기가 증가되어도 탐색할 때도 괜찮은 알고리즘 입니다. 하지만 문제가 있는데 바로 성장하는데 규칙이 너무 간단하다보니 규칙적으로 자라지 못하게 되는 경우가 있습니다.

위 그림을 보시면 한쪽으로만 치우쳐서 트리가 자라고 있는 것을 볼 수 있습니다. 저렇게 될 경우 검색 속도 또한 현저하게 떨어지게 되는 것입니다. 앞으로 우리가 계속해서 공부해볼 레드 블랙 트리하는 트리 알고리즘은 이러한 문제에 대한 답을 가지고 있는 이진 탐색 트리입니다. 레드 블랙 트리가 순수한 이진 탐색 트리와 다른 점이라면 노드를 빨간색 또는 검은색으로 표시한다는 정도가 전부입니다. 이러한 노드들의 색은 레드 블랙 트리에서 전체의 균형을 유지할 수 있게 해주는 아주 중요한 비결입니다.

그렇기 때문에 앞으로 구현해야할 레드 블랙 트리 노드의 구조체에는 다음과 같이 색깔을 위한 필드를 따로 마련해야합니다.

typedef struct tagRBTNode 

{

struct tagRBTNode* Parent; // 부모노드를 가리키는 포인터

struct tagRBTNode* Left;        // 왼쪽 노드를 가리키는 포인터

struct tagRBTNode* Right; // 오른쪽 노드를 가리키는 포인터

enum { RED, BLACK } Color; // 빨간색,검은색 색정보를 나타내는 변수

ElementType Data; // 데이터 변수

} RBTNode, *PRBTNode;

레드 블랙 트리가 균형을 유지하는 비결

레드 블랙 트리는 다음 규칙을 지킴으로써 균형을 유지합니다. 앞서 말했듯이 색정보와 아주 밀접한 관련이 있기 때문에 모든 규칙이 색과 관련되어 있습니다.

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

2. 루트 노드는 검은색이다.

3. 잎 노드는 검은색이다.

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

5. 루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.

잘 보시면 위 규칙들하고 잘 맞는 트리라는 것을 알 수 있습니다. 여기서 한가지 설명할 것은 잎 노드가 전부 NIL로 표시된 것입니다. NIL 노드는 아무 데이터도 가지고 있지 않지만 색깔만 검은색인 더미 노드입니다. 아무 데이터도 가지고 있지 않은 이 노드를 굳이 저장 공간을 할애해가며 사용하는 이유는 레드 블랙 트리를 구현하기 쉽게 하기 위해서입니다. 원래의 잎 노드들이 검은색이든 빨간색이든 NIL 노드를 양쪽 자식으로 연결해서 NIL 노드가 잎 노드가 되면 "모든 잎 노드는 검은색이다" 라는 규칙 하나는 항상 유지시킬 수 있기 때문입니다.

다음 시간엔 레드 블랙 트리의 기본 연산인 회전 부분부터 봐보도록 하겠습니다.

탐색은 어짜피 레드 블랙 트리나 이진 트리나 규칙이 같기 때문에 탐색은 제외하고 삽입과 삭제까지 포스팅을 앞으로 계속 해나가보겠습니다. 

일 끝나고 집에와서 뭐 할까하다가 맘편하게 책보면서 포스팅하는게 가장 마음이 편할 것 같아서 이러고 있습니다. 또한 레드 블랙 트리는 앞으로 제가 해야할 목록에 포함이 될 것 같아 부지런히 해야겠습니다. :D

그리고 아래 링크는 레드블랙트리 작동 방식을 쉽게 이해할 수 있도록 만들어 놓은 사이트입니다.

그런데 직접 사용해본 결과 "뇌를 자극하는 알고리즘" 책과 작동방식이 살짝 다른데 그냥 삽입 삭제 시 수행해야할 단계의 순서만 변경됬을 뿐 결국 결과와 효율은 같습니다.

http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html