개발 공부 - [검색트리] 레드블랙트리 - 2

INSERT

- 보통의 BST에서처럼 노드를 INSERT한다.

- 새로운 노드 z를 red노드로 한다.

- 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] < key[y]

          then left[y] <- z

          else right[y] <- z

 left[z] <- nil[T]

 right[z] <- nil[T]

 color[z] <- RED

 RB-INSERT-FIXUP(T, z)

FIXUP

레드블랙트리의 규칙이 위반될 가능성이 있는 조건들

각 노드는 red 혹은 black이다.

위반 가능성 없음

루트노드는 black이다.

새로운 노드 z가 루트 노드라면 규칙 위반, 아니라면 위반 가능성 없음

새로운 노드 z가 루트 노드라면 간단하게 노드를 블랙으로 바꾸는 작업을 해주면 된다.

모든 리프노드(즉, NIL 노드)는 black이다.

새로운 노드의 자식들을 NIL노드로 설정하므로 위반 가능성 없음

red노드의 자식노드들은 전부 black이다.(즉, red노드는 연속되어 등장하지 않고)

위반 될 가능성이 있다. 부모 노드가 원래 RED였다면, RED - RED 가 되므로 위반이 발생한다.

가장 큰 문제가 되는 것이 RED - RED 조건을 위반 하는 것이다.

모든 노드에 대해서 그 노드로 부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다.

새로운 노드를 RED로 추가 했으므로, 위반 가능성 없음

Loop Invariant (루프를 돌면서 변하지 않고 유지되는 조건) :

z는 red 노드

오직 하나의 위반만이 존재한다.

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

조건 4 : z와 그 부모 p[z]가 둘 다 red 이거나.

: 조건 4를 해결하기 위해 부모노드를 타고 올라가다 보면, 또다른 RED - RED 위반이 있을 수 있다. 최악의 경우 루트노드까지 타고올라가게 되면, 조건 2를 위반 한 것이므로 루트노드를 블랙으로 바꿔주고 종료하면 된다.

종료조건 :

부모노드 p[z]가 black이되면 종료한다. 조건2가 위반일 경우 z를 블랙으로 바꿔주고 종료한다.

INSERT의 시간복잡도

- BST에서의 INSERT : O(logn)

- RB-INSERT-FIXUP

Case 1, 4에 해당할 경우 z가 2레벨 상승한다.

Case 2, 3, 5, 6에 해당할 경우 O(1)

따라서, 트리의 높이에 비례하는 시간복잡도를 가진다.

즉, INSERT의 시간복잡도는 O(logn)

참고: https://ict-nroo.tistory.com/71?category=698685