이 친구는 아무리 봐도 원리가 전혀 이해되지 않는다. 특히 분류를 어떻게 했는지가 의문이다.
특히 케이스 분류가 너무 어렵다
Violation
일단 코드의 작동은 violation으로부터 시작 되는 것 같다.
RB tree의 큰 성질 5개
- Every node is either red or black.
- The root is black.
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
이런 성질이 5개가 있다.
여기서 하나하나 따져 보자
- 항상 충족된다.
why? 색을 2개만 정해 놓았기 때문 - 항상 출발 노드는 블랙일수 밖에없다.
why? root은 sentinel을 향하게 만들어 놓았기 때문이다
예외: 하지만 처음 삽입하는 것은 무조건 red이기 때문에 root가 black으로 만들어 줘야할 violation이 생긴다. - 이것도 항상 충족!
why? leaf node는 항상 sentinel을 향하게 만들어 놓았기 때문이다
- 여기가 중점 violation
If a node is red, then both its children are black.
- 이것도 충족한다
why? 삽입하는 것은 red이기 때문에 영향력이 없다
이렇게 violation 4가 중요한것을 깨닫고 case에대해서 생각해보자
일단 while문을 도는 이유는 z의 parent가 black이기 까지를 계속 도는 것이다.
그렇다면 다 정리(색과 숫자를 맞추는 것)되기 전까지는
maintenance
-
z의 parent가 조부모(zpp)의 left인지 right인지?
현재 코드는 zp가 left인지만 -
일단 zpp는 존재하는 것으로 나타나진다.
왜냐 zp가 빨강이면 그 위에는 무조건 존재하는 것이므로, 만약 루트라면 검은색이 된다. -
zpartent의 sibling의 색으로 인해서 {case1} {case2, case3} 이렇게 나눠진다.
-
(1) zp의 색, 즉 uncle의 색이 빨강이라면 case1로 들어간다
(2) uncle색이 검은 색이라면 case2, 아니면 case3로 들어간다 -
어찌됫든 간에 zpp는 검은색이다. 왜? zp가 빨간색이므로
-
결과적으로 z와 zp의 color violation이 유일한 violation인것은 확실하다
case1
case1은 zp랑 y가 둘다 빨간색일때이다
일단 uncle와 zp를 둘다 검은색으로 칠해버린다. (violation4)
그리고 zpp를 빨간색으로 칠해버린다. (violation 5)
그리고 zpp의 포인터를 2계단 올린다.
z' = zpp가 되는 것이다
즉 property 5을 보존하기 위해서 이렇게 위에를 다 색칠해주는 것이다.
만약 이렇게 zpp를 색칠햇는데 violation이 생긴다면 두가지 케이스가 존재한다.
1. 만약 zpp=z' 루트라면 이것은 p2가 문제가 생기는 것이다.
2. 만약 루트가 아니라면 p4가 문제가 생기는 것이다 z'p가 검은색이었으면 violation of p4가 없을 것이다. z' z'p간의 문제가 생기는 것이 빨간색이다.
한마디로 case를 나눌 때 uncle이 빨간색이라면 색을 맞춰주면 된다. 포인터를 올리고
case2,3
case2와 case3라면 즉 uncle color가 검은색이라면
이뜻은 z부모는 빨간색이고 uncle은 검은색인 상황이다
근데, uncle이 null이 될 수도 있지 않나?
일단 의식의 흐름을 따라가 보자
z가 왼쪽자식인지 오른쪽 자식인지 나누는 것이다.
여기서 property 5가 violation이 이루어 지는 데, 일단 black node기 때문에 상황은 violation of 5가 생긴다.
이를 고치기 위해서는 평균치를 만들어 줘야한다.
항상 case2, case3를 생각해봤을 때, case3를 만들어 줘야한다.
엇? 잠시만 그게 아니라 black weight는 다 같은 상황이라면 violation5가 성립할 수 가 없는데?
한마디로 균형은 이미 맞춰져 있다?
근데 왜 균형이 맞춰져 있지 ?
이미 맞춰져있는 상태, 즉 uncle이 오른쪽으로 균형이 맞춰져 있다 아무리 까만색이라도 균형자체는 맞춰져있는 상태이다.
왜 내가 이렇게 생각하기 어려울까? red node를 무시하기 어려워서?
일단 case2인 경우에는 left rotation을 돌려준다. 그렇게 되더라도 빨간색끼리의 rotation이니까 5에는 violation을 주지 않는다 그냥 violation of 4를 계속 떠 앉고 있는것이다.
- case2 완료
이제 4를 맞춰주기 위해서 즉 아직 uncle이 검은 색인 상황이다
그랫을 때 얘를 고쳐주는 방식이 right rotation이다. 물론 rotation을 하게 되면
violation 이 생기게 된다. 즉 B의오른쪽이 C밑으로 갔을 때 violation이 되게 된다.근데 color change로 하게 된다. 이것을 +- 방법으로 정리하면 더 좋을 것같다. 근데 왜 이렇게 균형을 맞추는 것인지는 나도 조금 이해하기 어렵다.
정리를 하려고 한 pdf
기존 메커니즘 이해하기
