Tree - 레드 블랙 트리(Red Black Tree) - 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | RB-DELETE(T,z) if left[z] = nil[T] or right[z] = nil[T] then y<-z else y<-TREE-SUCCESSOR(z) if left[y]!=nil[T] then x<-left[y] else x<- right[y] p[x]<-p[y] if p[y]=nil[T] then root[T] <- x else if y = left[p[y]] then left[p[y]] <- x else right[p[y]] <- x if y!=z then key[z] <- key[y] copy y`s satellite data into z if color[y] = BLACK then RB-DELETE-FIXUP(T,x) return y | cs |
레드 블랙트리 주요 연산중에서 마지막인
Delete 연산을 알아보자
위의 슈도 코드는 여러가지 조건문들이 많지만 간결하게
1) 보통의 BST 처럼 Delete 한다.
2) 실제로 삭제된 노드 y 가 RED였다면 종료
3) y가 Black이었다면 RB-DELETE-FIXUP을 호출한다.
레드 블랙 트리의 조건을 다시 살펴보자면
1) 각 노드는 red 혹은 black이다.
2) 루트 노드는 black이다.
3) 모든 leaf 노드(즉, NIL 노드)는 black이다.
4) 레드 노드 등의 자식들은 모두 black이어야한다.(레드가 연속해서는 안됨)
5) 모든 노드에 대해서, 그 노드로 부터 자손인 리프 노드에 까지 이르는 모든 경로에는
동일한 개수의 블랙 노드가 존재해야한다
이다.
RB-DELETE-FIXUP(T,x)에서 위의 조건을 비춰 보았을 때
1) OK
2) y가 루트였고 x가 red인 경우 위반
3) OK
4) p[y]와 x 모두가 red일 경우 위반
5) 원래 y를 포함했던 모든 경로는 이제 black 노드 하나가 부족
- 1. 노드 x에 "extra black"을 부여해서 일단 조건 5를 만족
- 2. 노드 x는 "double black" 혹은 "red & black"
Insert는 6가지의 경우가 있었는데 Delete는 8가지의 경우가 있다.
그러나 Insert와 마찬가지로 대칭되는 상황이므로 4개의 경우만 고려한다.
(x가 부모의 왼쪽인 경우, x가 부모의 오른쪽인 경우)
경우 1은 형제노드 w가 red인 경우이다.
w가 red이므로 반드시 자식 노드를 가져야하며, 자식 노드는 둘다 black 이된다.
더하여, 자식노드들은 nil 노드 일수가 없다.(조건 5에 위반이므로)
이 경우에 x의 부모 b에 대해 left-rotate를 진행한다.
이때 b와 d 는 위치 뿐만아니라 색까지 변경된다.
노드 x는 레벨이 한칸 내려가지만 아직 double black 노드이다.
두 번째 경우는 w의 두 자식노드가 둘다 black 인 경우이다.
여기서 x는 double black 노드이고 w는 그냥 black 노드이다.
따라서 x, w에서 black을 하나씩 뺏어서 노드 B에게 주는 것이다.
이렇게 하게되면, 위에서 밑으로 내려오는 경로상의 black 노드의 개수는 변화가 없다.
대신, node x는 double black에서 그냥 black 노드가 되었고
노드 w는 red 노드가 되었다.
문제는 둘의 부모 노드가 extra black 을 하나 넘겨받았으므로
원래 부모노드가 red였다면 검은공은 받아서 red black이 된다.
red black 이면 빨간공을 뺏고 끝이난다.
그러나 부모노드가 black노드였다면 부모노드가 새로운 double black노드가 된다.
3번째 경우는 w는 black, w의 왼쪽 자식은 red인 경우이다.
이때 w에 대해 right rotate연산을 적용한다.
연산이 실행되면 D와 C의 자리와 컬러가 바뀌게 된다.
결론적으로 D가 red가 되면 경우 4로 넘어가게 된다.
경우 4는 w가 black, w의 오른쪽 자식이 red인 경우이다.
이런 상황에서는 먼저, 노드 b(x의 부모)에 대해서 left rotate를 실행한다.
그리고나서, x의 extra black을 제거하고 종료한다.
결론적으로, 이러한 경우는 조건에 따라 순환하거나 다른 경우로 넘어가며
이에 대한 순서도는 위의 그림과 같다.
1,2,3,4와 5,6,7,8은 대칭적이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | RB-DELETE-FIXUP(T,x) while x!= root[T] and color[x] = BLACK do if = left[p[x]] then w <- right[p[x]] if color[w] = RED then color[w] <- BLACK // Case 1 color[p[x]] <- RED // Case 1 LEFT-ROTATE(T,p[x]) // Case 1 w <- right[p[x]] // Case 1 if color[left[w]] = BLACK and color[right[w]]=BLACK then color[w] <- RED // Case 2 x <- p[x] // Case 2 else if color[right[w]]=BLACK then color[left[w]] <- BLACK // Case 3 color[w] <- RED // Case 3 RIGHT-ROTATE(T,w) // Case 3 w <- right[p[x]] // Case 3 color[w] <- color[p[x]] // Case 4 color[p[x]] <- BLACK // Case 4 color[right[w]] <- BLACK // Case 4 LEFT-ROTATE(T,p[x]) // Case 4 x <- root[T] // Case 4 else (same as then clause with "right" and "left" exchanged) color[x] <- BLACK | cs |
마지막으로 RB-DELETE FIXUP의 슈도코드는 위와같다.
코드 안에서 조건문으로 1~4까지의 경우를 모두 처리해주게 된다.
종합적으로, 경우 1에서 4까지의는 위의 그림과 같이 동작하게 된다.
시간복잡도는 BST에서 DELETE를 해주고, FIXUP 연산을 이어서 해줘야한다.
두 연산의 시간 복잡도는 각각 
최종 시간 복잡도는 
레드 블랙 트리에 대한 강의를 들었는데,
이해를 못하고 그냥 저장용으로 적어놓은 느낌이 크다.
다른 알고리즘과 다르게 Case가 많이 발생하고 연산이 복잡해서 한번에 들어오지 않는다.
레드 블랙 트리에 관한 내용을 찾아서 읽거나 한번 더 강의를 들어서 꼭 이해해야 할듯하다.
유튜브를 찾다가 레드블랙트리를 표현한 동영상 링크들이 있어서 첨부한다.
'알고리즘 문제풀이' 카테고리의 다른 글
| [알고리즘] 해싱(Hashing) - 2 (0) | 2017.05.09 |
|---|---|
| [알고리즘] 해싱(Hashing) - 1 (0) | 2017.05.09 |
| [알고리즘] Tree - 레드 블랙 트리(Red Black Tree) - 2 (0) | 2017.04.19 |
| [알고리즘] Tree - 레드 블랙 트리(Red Black Tree) - 1 (0) | 2017.04.19 |
| [알고리즘] Tree - 이진 검색 트리 - 3 (0) | 2017.04.19 |
댓글