hello world
레드 블랙 트리 2 본문
INSERT ..
보통의 BST에서처럼 노드를 INSERT한다.
새로운 노드 z를 red노드로 한다.
PB_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)
위반될 가능성이 있는 조건들
1.각노드는 red혹은 black( 위반 가능성 없다)
2. 만약 z가 루트노드라면 위반, 아니라면 OK.(위반될 유일한 경우 원래 트리가 empty노드였다면)
3. 모든 NIL 노트는 black(위반가능성없다)
4. RED가 연속해서는 안된다 Z의 부모 p[z]가 red이면 위반.(위반가능성 있음)
5. 자손까지 내려가는 모든 경로에 black노드의 갯수는 동일해야한다.(위반가능성 없음)
Loop Invariant :
-Z는 red노드
-오직 하나의 위반만이 존재한다.
조건2 : z가 루트노드이면서 red이거나, 또는
조건4 : z와 그 부모 p[z]가 둘 다 red이거나
종료조건:
부모노드 p[z]가 black이되면 종료한다. 조건2가 위반일 경우 z를 블랙으로 바꿔주고 종료한다.
1.z의 부모의 형제가 RED인 경우
-새로운 노드 z의 부모가 red이면서 부모의 형제노드 D가 RED인 경우이다.
-이 경우 부모노드와 부모노드 형제노드를 BLACK으로 바꾸고 할아버지노드를 RED로 바꿈
-할아버지 노드 C를 새로운 노드 z로 설정 위로 올라가면서 위반검사
-case1을 반복할 때 트리의 높이보다 여러번 반복될수없다.
2.Cas 2,3 : Z의 부모의 형제가 BLACK인 경우
Case2 : Z가 오른쪽 자식인 경우
p[z]에 대해서 left-rotation한 후 원래 p[z]를 z로 만든다
Case3 할아버지 중심으로 right-rotation
case1,2,3,은 p[z]가 p[p[z]]의 왼쪽 자식인 경우들
case 4,5,6은 p[z]가 p[p[z]]의 오른쪽 자식인 경우들
PB-INSERT-FIXUP 수도코드
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[y] = RED
then color[p[z]] <- BLACK >> CASE 1
color[y] <- BLACK >> CASE 1
color[p[p[z]]] <- RED >> CASE 1
z <- p[p[z]] >> CASE 1
else if z = right[p[z]]
then z <- p[z] >> CASE 2
LEFT-ROTATE(T, z) >> CASE 2
color[p[z]] <- BLACK >> CASE 3
color[p[p[z]]] <- RED >> CASE 3
RIGHT-ROTATE(T, p[p[z]]) >> CASE 3
else(same as then clause with "right" and "left" exchanged)
color[root[T]] <- BLACKINSERT의 시간복잡도
-BST에서의 INSERT : O(log2n)
-RB-INSERT-FIXUP
-경우 1에 해당할 경우 z가 2레벨 상승
-경우 2,3에 해당할 경우 O(1)
-따라서 트리의 높이에 비례하는 시간
-즉, INSERT의 시간복잡도는 O(log2n)
참고