삭제
doubly black의 extra black을 없에는 4 cases
case 4
case 4 - 더블리 블랙의 오른쪽 형제가 블랙 & 그 형제의 오른쪽 자녀가 red & 그 형제의 오른쪽 자녀가 black
아이디어
색바꿔주기
회전하기
회전 후 모습
더블리 블랙을 모아서 위로 보낸다
그랬더니 레드앤블랙 됨
red and black은 색을 black으로 바꾸고 extra black을 제거하면 문제 해결
아래는 문제 해결 모습
case 4 해결하는 위 과정을 간략하게 하는 방법
1번 - 오른쪽 형제의 색을 그 부모의 색으로, 오른쪽 형제의 부모와 자녀를 black으로 바꾼다.
바꾼 모습
2번 - 부모를 기준으로 왼쪽으로 회전
case 3
case 4는 더블리 블랙의 오른쪽 형제가 블랙 & 그 형제의 오른쪽 자녀가 red & 그 형제의 오른쪽 자녀가 black
이었다면
case 3은 더블리 블랙의 오른쪽 형제가 블랙 & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀가 black
해결 아이디어
case 4처럼 레드의 위치를 오른쪽으로 바꿔주면 case4 처럼 해결할 수 있지 않을까?
해결 방법
-
C (red)와 D의 색을 바꾼다.
바꾼 모습
-
D를 기준으로 오른쪽으로 회전
- D를 기준으로 오른쪽으로 서브트리가 내려오고
- C를 기준으로 서브트리가 올라가고
- C의 오른쪽에 붙어있던 q서브트리는 D의 왼쪽에 붙여준다.
회전 완료한 모습 (5번속성 만족함)
위 모습은 case 4에 해당하는 모습이기 때문에 case4의 해결방식으로 해결해주면 된다.
-
색깔 바꿔주기
-
회전 시켜주기
case 3 해결 요약
case 2
doubly black 형제가 black & 형제의 두 자녀 모두 black
해결 아이디어
doubly black과 형제의 black 모아서 부모한테 extra black 해결 하게 하기.
해결 방법
- 블랙 모아서 부모한테 던지기
그러면 위와 같은 모습이 되는데, 부모가 red라면 red and black이 되고 부모가 black이면 doubly black 됨 - rnb 면 black으로 바꾸고 db면 B가 루트이면 black으로 바꾸고 아니라면 case 1,2,3,4 중 하나로 해결
해결 방법 정리
case 1
db 형제가 red일 때. case 2,3,4모두 db형제가 black 이였음.
해결 아이디어
db 형제를 black으로 만들면 case 2,3,4중에 하나로 해결 될텐데 어떻게 바꾸지?
B를 기준으로 회전하면 A와 C가 형제가 됨..!
여기서 중요한 건 회전하면 red가 B자리에 가서 5번 속성이 깨진다. 따라서 회전 전에 B와 D의 색을 바꿔준다. 아래는 색 바꿔준 모습.
그리고 회전하고 나면 아래와 같은 모습이 된다.
해결 방법 정리
삭제 시간 복잡도
이진 탐색 트리에서는 삭제가 O(N) 이였는데 레드블랙트리에서는 average와 worst 모두 O(logN)으로 상당히 향상된 모습이다.
RB tree VS AVL tree
- AVL 트리는 Balace factor를 루트까지 계산해서 발란스를 맞추며 삽입 삭제를 하기 때문에 삽입 삭제에서는 rbtree에 비해 성능이 더 느리다.
- 검색 성능은 둘다 O(logN)이기 때문에 큰 차이는 아니지만, AVL트리가 균형을 더 엄격하게 잡기 때문에 균형이 더 낫다는 뜻은 검색 속도가 더 빠르다는 뜻.
- 응용 사례가 AVL은 검색을 자주 하고 한번 만들면 삽입 삭제가 적은 것. 예를들어, 사전 같은 곳에서 드물게 쓰인다. 반면 rbtree는 쓰이는 곳이 많다. 아무래도 검색 성능이 거의 비슷한데 삽입 삭제 성능이 좋기 때문이겠다.
