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

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

이어서 레드 블랙 트리의 insert연산에 대해 알아보자

순서는 다음과 같다.

1) BST에서 처럼 노드를 insert한다.

2) 새로운 노드 z를 red 노드로 한다.

3) RB-Insert-fixup을 호출한다.

RB-INSERT(T,z){
    y<-nil[T]
    x<-root[T]
    while x!= nil[T]
        do y <- x
            if(key[z]<key[x])
                then x <- left[x]
                else x <- right[x]                                                                       
    p[z] <-  y
    if y = nil[T]
        then root[T] <- z
        else if key[z] <- z
            then left[y] <- z
    left[z] <- nil[T]
    right[z] <- nil[T]
    // 여기서 부터 BST와 다름
    color[z] <- RED
    RB-INSERT-FIXUP(T,z)
}

우리가 삽입된 노드를 Red로 설정했기 때문에

Red가 2개 중복되기 때문에 조건에 위반될 가능성이 존재한다.

따라서 RB-INSERT-FIXUP 함수를 호출해서 이를 해결한다.

레드 블랙 트리의 조건을 다시 한번 살펴 보자

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

2) 루트 노드는 black이다.

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

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

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

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

위와 같은 조건에 insert연산을 진행한다면 예외적인 상황은 다음과 같이 발생할 수 있다.

1)OK

2) 만약 z 가 루트 노드이면 위반, 아니라면 OK

3)OK

4) z의 부모 p[z] 가 red라면 위반

5)OK

따라서 루트를 도는 동안 유지되는 조건(Loop-Invariant)은 

z는 red 노드이며 위의 위반조건(2번, 4번) 중 오직 하나만 존재해야한다는 것이다.

조건 2: z 가 루트 노드 이면서 red이거나

조건 4:  z와 그 부모 노드 p[z]가 둘다 red일 때

종료 조건은 부모노드 p[z]가 black이 되면 종료한다.

조건 2가 위반일 경우 z를 블랙으로 바꾸어 주고 종료한다.

몇가지 케이스를 살펴보자

케이스 1,2,3은 p[z]가 p[p[z]]의 왼쪽 자식인 경우이며

케이스 4,5,6은 p[z]가 p[p[z]]의 오른쪽 자식인 경우이다.

1,2,3과 4,5,6은 대칭적인 상황이므로 1,2,3을 집중해서 보도록 한다.

Case 1 :  z 의 삼촌이 red

노드 z가 레드이고 z의 p[z]도 레드인데 p[z]가 p[p[z]]의 왼쪽 자식일 때 이며

z의 삼촌(y 노드)가 레드인 경우이다.

p[z]와 삼촌의 칼라와 p[p[z]]의 컬러를 바꾸어준다.

이 연산을 했다고 하더라도 이진 트리의 구조는 바뀌지 않는다.

또한 레드에서 블랙으로 바뀐 노드의 자식들도 원래 블랙이었으므로

색상에 있어서 큰 오류는 없다.

다만 p[p[z]]노드의 색상이 바뀌었으므로 p[p[z]]의 부모와 p[p[z]] 노드의 관계를 재 정립 해야한다.

최악의 경우는 이러한 관계정립이 루트 노드까지 올라간다.

결과적으로 case1은 문제가 해결되지 않았지만 z가 2칸 올라간것을 확인할 수있다.

Case 2, 3 : z의 삼촌이 black

Case 2 : 내가 내 부모의 오른쪽 자식일 때

p[z]에 대해서 left-lotation 한 후, case 3 로 이동한다.

Case 3 : 내가 내 부모의 왼쪽 자식일 때

p[z]를 black, p[p[z]]를 red로 바꾼다.

p[p[z]]에 대해서 right rotation 을 진행한다.

이렇게 case 3까지 진행되면 모든 문제가 해결 되었음을 알 수 있다.

RB-INSERT-FIXUP(T,z){
    while color[p[z]]=RED
        do if p[z] = left[p[p[z]]]
            then y <- right[p[p[z]]]
                if(color[p[z]]<-black)
                    then color[p[z]]<-BLACK
                         color[y]<-BLACK
                         color[p[p[z]]]<-RED
                         z<-p[p[z]]
                else if z=  right[p[z]]
                    then z<-p[z]
                        LEFT-ROTATE(T,z)
                    color[p[z]]<-BLACK
                    color[p[p[z]]]<-RED
                    RIGHT-ROTATE(T,p[p[z]])
        else(same as then clause with "right" and "left" exchanged)                                         
color[root[T]]<-BLACK
}        
 

Insert 연산의 슈도 코드이다.

BST에서의 시간 복잡도는 O()

RB-INSERT-FIXUP은 

case1 일 경우 z가 2레벨 상승,

case2,3 일 경우 O(1) 이므로

높이에 비례하게 된다.

즉, INSERT 연산의 시간 복잡도는 O()이다

위의 그림이 레드 블랙 트리의 Insert연산에 대한 예시 이다.

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