2008.12.23 13:24

원문 http://blog.naver.com/kimsk99/50003121515

STL을 공부하다보면 STL에서 검색이 필요한 자료구조는 모두 red-black tree로 되어 있다는 것을 알 수 있다.

그동안 대충 balanced tree의 일종이라는 것 정도만 알고 있었다.

최근에 red-black tree에 대해서 적어놓은 어떤 글을 보고 구체적으로 어떤 트리인지를 조사해 보았다.

 

이글은 아래의 싸이트에 나오는 설명을 참조해서 정리한 것이다.

 

  Sorting and Searching Algorithms

 

-----------------------------------------------------

 

Red-black tree(이하 RB트리)는 binary search tree를 확장시켜서 balance 기능을 추가 시킨 트리이다.

RB트리의 정의는 아래의 5가지이다.

 

속성 1. 모든 노드는 red나 black의 색깔을 갖는다.

속성 2. 모든 리프(leaf)는 센티넬 노드(sentinel node)로서 black이다.

속성 3. 만약 어떤 노드가 red라면 그 노드의 두 자식은 모두 black이다.

속성 4. 루트(root)에서 리프로의 경로를 생각할 때, 모든 경로에 대해서 black의 숫자는 같다. (이것을 black height라고 한다.)

속성 5. 루트는 항상 black이다.

 

RB트리는 위의 5가지 속성을 유지하도록 연산을 정의하는 것이다.

위의 5가지 속성에 의해서 RB트리는 leaf까지 최대 길이의 차이가 2배 범위 안에 놓이게 된다.

(이것은 B-B-B처럼 B로만 된 leaf까지의 경로가 최적의 경로이고, B-R-B-R-B처럼 RB가 섞인 경로가 최악이다.

이때 적의 경로와 최악의 경로의 차는 2배이다.)

5가지 속성을 유지하는데 드는 비용은 insert, delete에 평균적으로나 최악의 경우 log(n)이 들어간다.

 

RB 트리에서 리프를 센티넬 노드라고 표현하고 있다.

이것은 리프가 내부에 값을 갖는 노드가 아니라 일종의 더미 노드이기 때문이다.

보통 리프의 구현 즉 센티넬 노드의 구현은 공용 센티넬 노드를 만들고 그것을 참조하는 형태로 사용한다고 한다.

 

*. 노드 삽입

노드 삽입를 위해서 먼저 binary search tree에 대한 노드 삽입 알고리즘대로 노드를 일단 추가한다.

당연히 새롭게 삽입된 노드는 기존의 센티넬 노드의 자리에 추가되어야 한다.

즉 새 노드는 두개의 센티넬 노드를 자식 노드로 갖고 기존 센티넬 노드 자리에 들어가게 된다.

 

새롭게 삽입된 노드의 색깔은 무조건 R로 한다.

 

이렇게 된 트리는 현재  

 (1) 센티넬 노드 자리에 센티넬 노드를 자식으로 갖는 노드를 추가했기 때문에 속성 2, 5는 만족한다.

 (2) R로 했기 때문에 속성 1, 4를 만족한다.

 

위반할 수 있는 속성은 속성 3밖에 없다.

즉 다른 속성에 위반되지 않도록 하면서 속성 3을 만족하도록 트리를 변경해 주면된다.

 

속성 3을 위반하는 경우는 새로운 노드의 부모 노드가 R인 경우 밖에 없다.

이때에 대한 처리 방법은 아래의 2가지로 나뉜다.

 

A. 부모가 R, 삼촌도 R

부모가 R이라면 할아버지는 반드시 B여야 한다.

(기존 트리가 RB트리 속성을 모두 만족하기 때문에 연속된 R을 갖을 수는 없다.)

부모와 삼촌이 모두 R이라면 아래의 그림처럼 부모와 삼촌을 B로 바꾸고 할아버지를 R로 바꾼다.

이렇게 하면 모든 노드의 black height는 보전된다.

 

새롭게 생긴 R노드, 즉 할아버지 노드에 대해서는 지금 적용한 삽입후 처리 알고리즘을 재귀적으로 적용할 수 있다.

할아버지 노드는 R노드이고 B를 자식으로 갖기 때문에 새롭개 삽입된 노드의 특징을 모두 지니기 때문에 같은 알고리즘이 적용될 수 있다.

 

만약 할아버지 노드가 루트 노드라면 할아버지 노드를 다시 B로 칠하면 된다.

이 경우는 전체 트리의 black height가 1증가하게 된다.

 

 

 

 

B. 부모가 R, 삼촌은 B

부모가 R이고 삼촌이 B인경우는 아래의 그림과 같이 트리 전체를 한칸 밀어버리면 된다.

이렇게 밀어 버린다고 해서 binary search tree의 속성을 위배하지 않는다.

이 과정에서 모든 black height는 보전 된다.

 

 

위의 두가지 경우가 모든 경우의 수이다.

생각해보면 삼촌 노드가 존재하지 않는 경우가 있을 지도 모른다.

하지만 이런 경우는 트리의 정의에 의해서 없다.

모든 리프 노드를 일종의 더미 노드인 센티넬 노드로 만들어 버렸기 때문이다.

할아버지 노드에 값을 가지고 있는 아버지 노드가 존재하기 때문에 할아버지 노드는 센티넬 노드가 아니가.

그렇기 때문에 반드시 삼촌 노드가 존재해야 한다.

 

또 한가지 드는 의문점은 위의 그림에서 X가 A의 left가 아니라 right라면 어떻게 할 것이냐이다.

즉 위의 그림에서 c가 R인 경우로 위의 방법을 그대로 적용한다면 B, c가 R-R 이되어문제가 생긴다.

하지만 이런 때는 먼저 트리 이동을 수행해서 위의 그림처럼 X가 A의 left 상태로 만들 수 있다.

이것은 아래 그림의 두 트리는 모두 같은 의미의 binary search tree이기 때문에 가능하다.

(물론 위의 재배치가 가능한것도 이 특성을 이용한 것이다.)

 
 
*. 삭제
red-black tree의 노드 삭제 역시 기본은 binary search tree의 노드 삭제를 기본으로 한다.
Binary search tree의 삭제 원칙에 따라서 삭제될 노드는 항상 하나 이상의 센티넬 노드를 자식 노드로 갖는 노드가 된다.
이런 노드가 아닌 노드의 삭제시에는 연속자(succesor)를 대신 지우는 것으로 위의 조건을 만족하게 할 수 있다.
 
삭제 과정에서 지워진 노드가 R이라면 별도의 처리는 필요없이 모든 속성이 유지된다.
하지만 B라면 속성 4에 위배가 된다. (지워진 노드가 루트라면 예외이다.)
결국 속성 4를 다시 만족시켜 줘야 한다.
B가 지워졌기 때문에 black height가 1줄었다.
결국 다른 리프들에 대한 경로에 대한 black height가 1줄도록 변경해 줘야 한다.
이런 변경은 앞에서 본 삽입과정과 유사하게 처리될 수 있다.
Posted by 두장