[알고리즘] Tree - 레드 블랙 트리(Red Black Tree) - 1

Tree - 레드 블랙 트리(Red Black Tree) - 1  

앞서 본 이진 탐색 트리의 기본연산 3가지(Insert, Search, Delete)가

트리의 높이에 비례하는 시간복잡도를 가지고 있었다.

이때, 극단적으로 비대칭 적이며 높이가 높은 트리에서는 그 효율이 높지 않다.

따라서 이진 탐색 트리의 구조를 유지하며 안정성도 살리는 트리가 필요해졌다.

이 들 중 하나가 레드 블랙 트리이다.

레드 블랙 트리는 이진 탐색 트리의 일종이다.

이진 탐색 트리에서 Insert와 Delete 알고리즘을 적절하게 수정하여

이진 탐색 트리임에도 불구하고 트리의 높이에 상관없이 O(logN)의 시간복잡도를 유지해준다. 

레드 블랙 트리의 형태는 다음과 같다.

1) 각 노드는 하나의 키(key), 왼쪽 자식 노드, 오른쪽 자식 노드 그리고 부모 노드의 주소를 저장한다.

2) 자식 노드가 존재하지 않을 경우 NIL 노드 라고 부르는 특수한 노드가 있다고 가정한다. 

3) 따라서 모든 leaf 노드는 NIL 노드이다.

4) 루트의 부모 노드도 NIL 노드라고 가정한다.

5) 노드들은 내부 노드와 NIL 노드로 분류한다.

실제로 NIL 노드는 구현 단계에서 존재하지 않기 때문에 (b) 그림처럼 하나로 생각한다.

실재로 존재하는 데이터들은  (c)의 그림과 같다.

또한 레드 블랙 트리는 다음의 5개의 조건을 만족하는 이진 탐색 트리이다.

1) 각 노드는 red 혹은 black이다.

2) 루트 노드는 black이다.

3) 모든 leaf 노드(즉, NIL 노드)는 black이다.

4) 레드 노드 등의 자식들은 모두 black이어야한다.(레드가 연속해서는 안됨)

5) 모든 노드에 대해서, 그 노드로 부터 자손인 리프 노드에 까지 이르는 모든 경로에는 

동일한 개수의 블랙 노드가 존재해야한다

위의 조건을 만족하는 레드 블랙 트리이다.

1번 부터 5번까지 모든 조건을 만족함을 확인할 수 있다.

레드 블랙 트리의 높이(h(x))는

자신으로 부터 리프 노드까지 가장 긴 경로에 포함되는 엣지의 개수이다.

또한 레드 블랙 트리는 블랙 높이(Bh(x))라는 것이 있는데, 

이는, x로 부터 리프노드까지의 경로상의 블랙 노드의 개수이다.(노드 x 자신은 불포함)

위 그림에서 h가 높이 이며, bh가 블랙 높이이다.

블랙 높이는 어디로 내려가더라도 5번 조건으로 동일한 값이 된다.

여기서 알수 있는 것은

1) 높이가 h인 노드의 블랙 높이는 bh>=h/2이다.(조건 4에 의해 레드는 연속될 수 없으므로)

2) 노드 x를 루트로 하는 임의의 부트리는 적어도 2^(bh(x))-1개의 내부 노드를 포함한다.

3) n개의 내부 노드를 가지는 레드 블랙 트리의 높이는 이하이다.

레드 블랙 트리는 기본적으로 이진 탐색 트리 이기 때문에 Search 알고리즘은 동일하다.

남은 Insert, Delete를 하기 전에 Left/Right Rotation 연산을 알아야한다.

이것은 한 노드를 중심으로 노드의 모양을 변형하는 연산이다.

이 연산을 수행 하더라도 이진 탐색 트리의 특성을 유지한다.

Left Rotation을 수행하면 x와 y의 자리가 바뀌며 x는 y의 왼쪽 자식 노드가 된다.

또한 자식 노드의 위치도 왼쪽으로 조금 바뀐다.

Ritght는 이와 반대다.

LEFT-ROTATE(T,x){
    y <- right[x]
    right[x] <- left[y]
    p[left[y]] <- x
    p[y] <- p[x]
    if p[x] = nil[T]
        then root[T] <- y
        else if x = left[p[x]]
            then left[p[x]] <- y
            else right[p[x]] <- y                                                                           
    left[y] <- x
    p[x] <- y
}

Left Rotate의 슈도 코드이다

자세한 설명은 동영상을 참조하자.

Rotate 연산을 수행 했을 때 위와 같은 결과가 나온다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘