알고리즘 이론 13강. 레드블랙 트리(Red-black trees)

 

[레드 블랙 트리]

: 균형잡힌 트리의 유형중 하나.

: 각 노드마다 색깔을 가지게되는데, Red나 Black 중 한개를 가진다.

: 이 노드의 색을 이용해 루트에서 잎 노드의 경로에 나타나는 색을 제한해 균형을 유지한다. (아래에 자세히)

 

 

 

[레드블랙 트리의 특성]

: 다음 특성을 만족하는 이진 검색 트리를 레드블랙 트리라 한다. (중요)

1. 모든 노드는 적색 or 흑색 이다.

2. 루트는 흑색이다.

3. 모든 잎 이후의 노드, NIL 노드는 모두 흑색이다.

4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다. (흑색의 자식이 꼭 적색일 필요는 없지만, 적색의 자식은 꼭 흑색이여야 한다!)

5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은수의 흑색 노드를 포함한다.

  

 

 

[레드 블랙 트리의 예시]

Red-black tree example

- 노드의 높이 : 잎노드로 가는 가장 긴 거리 : 4

- 노드 x의 흑색 높이 : 자기 자신 x 의 색 포함하지 않고, NIL 색 포함한 경로까지의 블랙 노드의 개수 (47노드의 흑색 높이 : 1 )

 

 

 

[레드블랙 트리의 중요한 특성]

n개의 내부 노드를 가지는 레드블랙 트리는 최대 2log(n + 1)의 높이를 가진다.

: 이 사실을 증명하기위해선 다른 2가지 보조정리를 증명해야한다.

 

1. 어떤 노드 x 라도, 해당 노드의 위치 h(x)에 대해 bh(x) >= h(x)/2이다.

2. 루트가 노드 x인 서브트리는 적어도 2^(bh(x)) - 1 개의 내부 노드를 가진다.

# 1,2 번에 대한 증명 과정 생략

# 1,2 번을 이용한 중요한 특성 증명 과정 생략

 

 

 

[레드블랙 트리의 연산]

: SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR을 위 보조정리를 이용하면 모두 O(logn)의 시간에 구현가능함을 알수 있다.

: TREE_INSERT, TREE-DELETE 또한 O(logn)의 시간에 구현가능하다.

 

 

 

[레드블랙 트리의 삽입(INSERT)]

: 기본적인 삽입은 이진 트리의 삽입과 동일. 단 새로운 노드의 색깔이 무엇일지가 이슈이다.

: 삽입되는 위치의 부모노드가 레드인경우 : 레드의 자식은 반드시 블랙이여야 한다.

: 삽입되는 위치의 부모노드가 블랙인경우 : 블랙

 

 

[레드블랙 트리의 삭제(DELETE)]

: 제거된 노드의 색깔은 무엇이였는가?

- 모든 노드가 레드 or 블랙이다                                             : OK

- 루트가 블랙이다                                                              : NOT OK. root 삭제시 root 노드의 자식중 레드 노드로 변경발생 가능!

- 모든 잎 노드는 블랙이다                                                   : OK

- 노드가 레드면, 그 노드의 자식 노드는 블랙이다                      : NOK OK. row에 두 레드 노드 생성 가능!

- 각 노드로부터 경로들은 모두 같은수의 흑색 노드를 포함한다     : NOT OK : 특정 노드에서 흑색 높이 변경 가능!

 

# 레드블랙 트리의 삽입과 삭제 알고리즘은 따로 다루지 않겠습니다.