Algorithm #2. Search algorithm. - 2.5 Red-Black Tree (1).

이번에 소개할 Red-Black Tree 는 Binary search tree 의 일종입니다.
이전에 구현했던 Binary Search Tree 는 다음과 같은 node 구조체를 선언했었죠.


typedef struct node{ char dat; struct node *lLink; struct node *rLink; } bTree_node;

node 의 값을 저장할 변수와, 좌/우측 link node 의 값을 포함하는 구조체입니다.
하지만, Red-Black Tree 는 여기에서 '색깔' 을 저장할 추가 변수의 선언이 필요합니다.
다시말하면, 각 node 는 'Red' 혹은 'Black' 의 색깔을 갖는다는 것이죠.

그럼 이쯤에서 Red-Black Tree 의 필요성을 설명드려야 할 듯 합니다.

예전 포스트에서 Binary Tree 는 완벽하게 균형이 잡혀있을 경우엔 O ( log N ) 의 성능을 자랑한다는 말씀을 드렸을겁니다.
- Binary Tree 가 균형이 잡혀있다는 의미는 'Tree 의 level' 이 낮아진다는 것을 의미하니까요. -
하지만, Binary Tree 가 한쪽으로 치우친 Skewed Binary Tree 의 꼴을 취하면 취할수록 Tree 의 level 은 올라가고,
검색 시간도 그에 비례하여 증가합니다. 직관적으로 이해하실 수 있겠죠.

이런 단점들을 보완하기 위하여 여러 컴퓨터 과학자들이 연구를 거듭했습니다.
- 사실 Binary Tree 의 불균형 문제는 오랫동안 연구되어 온 주제 중 하나입니다. -
이들의 논제는 '어떻게 하면 주어진 자료집합으로 가장 효율적인 Balanced Binary Tree 를 조직할 수 있는가?' 였죠.

그에 대한 대표적인 이론이 바로 'AVL Tree' 와 'Red-Black Tree', 그리고 'Splay Tree' 였습니다.
그 중에서도 Red-Black Tree 는 자료집합의 연산에 대해서 최악의 경우 O ( log N ) 의 성능을 보장하게끔
균형을 잡아놓은 효율적인 검색 알고리즘 중 하나입니다.

- AVL Tree 란? : Adelson, Velskii, Landis 라는 세 연구가에 의해 소개된 알고리즘.
                        각 노드에 'Balance Factor' 를 주고, 이 값에 의거해 Tree 를 재조직하는 기법이다. -

다음은 Red-Black Tree 의 기본 구성방법입니다.
한국어로 된 책을 여러권 읽어봤지만, 내용이 너무 애매해서 -_-;;
'Introduction to Algorithms' 의 원문을 싣습니다.

1. Every node is either red or black.
     모든 node 는 적색 혹은 흑색이다.

2. The root is black.
     root 는 흑색이다.

3. Every leaf is black.
     모든 leaf 는 흑색이다.

4. If a node is red, then both its children are black.
     만약 한 node 가 적색이라면, 이 node 의 두 자식은 모두 흑색이다.

5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
     각 node 로부터, node 에서 자손까지의 모든 경로들은 같은 갯수의 흑색 node 를 포함한다(가진다).

- by Introduction to Algorithms, 2th,  MIT press.

저 중,

 '5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.'

에서부터 Black-height 라는 용어가 나옵니다.

즉, root node 에서부터 각 leaf node 까지의 경로에서, Black node 의 갯수는 모두 동일하다는 의미지요.
따라서, 한 개의 Red-Black Tree 에서 Black-height 는 단 하나로 정의할 수 있습니다.

그리고, n 개의 internal-node 로 구성된 Red-Black Tree 는 기껏해야 최대 2 log (n + 1) 의 탐색 level 을 갖습니다.
또한 Red-Black Tree 내에서 root 로부터 leaf 로 가는 가장 긴 경로의 길이는 가장 짧은 경로의 길이의 최대 2배라는 것이
알려져 있습니다.
최대 2배이상 길어질 수 없다는 의미죠. -_-a
따라서, 기존의 알고리즘보다 훨씬 효율적이라 할 수 있습니다.




Red-Black Tree 에 대해선 설명할 것이 꽤 됩니다.
따라서 포스트를 몇개로 끊어야 할 것 같네요.
다음은 Red-Black Tree 의 회전. 삽입. 그리고 가능하다면 삭제 방법까지 포스팅해보기로 하죠.

그리고 Red-Black Tree 의 포스트가 끝나면 AVL Tree, Splay Tree 순서로 포스팅을 합니다.