[Datastructure] Red-black 트리

참고 자료

😇 신찬수 교수님 자료구조 강의
geeksforgeeks

Red-Black 트리

개요

search, insert, delete를 O(log n) 시간 내에 처리할 수 있다.

AVL트리와 Red-Black트리에 비해 더 균형있지만, insert, delete과정에서 많은 rotation을 호출한다.
만약 insertion과 deletion이 많은 작업이라면, Red-Black트리를 적용하는 것이 더 선호된다.

만약 insertion과 deletion보다 search가 더 많이 호출되는 작업이면 AVL트리를 적용하는것이 더 낫다.

전제조건)

1. None을 leaf노드로 표현한다, 내부노드는 None노드를 제외한 노드이다.
2. 모든 노드는 색을 가져야하고, red-black순이다.
3. root노드는 black이다.
4. None 노드는 black이다.
5. red노드의 자식노드는 black이다.(black의 자식은 black일수도있다.)
6. <중요>각 노드에서 leaf(None)노드로 가는 경로 중에 만난 black노드의 개수가 항상 같아야한다.

높이증명

전제조건 6이 중요한 이유는 이 6번으로 인해 전체 트리의 균형이 맞기 때문이다.

삽입연산

red-black 트리에서는 rebalancing을 위해

1. Recoloring
2. Rotation 을 한다.

삽입할 노드를 x, x의 부모노드를 p, p의 부모노드를 g, g의 p가 아닌 자식노드를 u라고하자.

Recoloring

red 노드를 black으로 바꾸거나, black노드를 red 노드로 바꾸는 것을 Recolouring이라고한다.
단, None 노드는 항상 black으로 유지되어야한다.

항상 recolouring을 먼저 시도하고, 만약 recolouring이 작동하지 않는다면 rotation을 한다는 것이다.

알고리즘 로직은 크게 2가지가 있는데, u의 색이 red인경우, recolour를 한다.
u의 색이 black인 경우, rotation과 recolour를 동시에 하거나 둘 중 하나를 해야한다.

로직

1. 새로운 노드x를 만들어 BST insert에 따라 삽입을 한다.
2. 그리고 이 노드에 red를 부여한다.

3. 만약 이 노드가 root노드라면 black으로 색칠한다.

4. root노드가 아니라면 부모노드p의 색을 확인한다.
5. 부모노드p의 색이 black이라면 새 노드의 색을 바꿀필요가 없지만, red라면 바꿔야한다.

6. 부모노드p의 색이 red일때, u의 색을 확인해야한다.

   a). u의 색이 red라면 p의 색과 u의 색을 black으로 바꾸고, g노드를 red로 바꿔야한다.
   b). g노드의 색이 바뀌었기 때문에, g의 부모노드들에 대해서도 색이 모두 바뀌어야한다.
   c). x에 g노드를 할당하고, 이 노드에 대해 색을 다시 검증한다.

7. u의 색이 black이라면 4가지의 경우가 생긴다.

   a)left-left g를 기준으로 right 회전 후 G와 P의 색을 바꾼다.

   b)left-right p를 기준으로 left 로테이션하면 left-left케이스가 되므로 left-left(a)를 적용한다.

   c)right-right g를 기준으로 left 로테이션하고 g와 p의 색을 바꾼다.

   d)right-left p를 기준으로 right 로테이션하면 right-right케이스가 되므로 right-right(c)를 적용한다.

삭제연산

삽입연산과같이 recoloring과 rotation으로 전제조건을 유지한다.

삽입연산과 다른점은, 삽입연산에서 case를 구별하기위해 u의 색에 따라 경우가 나뉘었지만,
삭제연산에서는 x의 형제노드 s로 경우를 구분한다는 것이다.

insertion이후 발생하는 전제조건 위반은 주로 2개의 연속적인 red node가 발생하는 것이었다.
deletion에서는 black노드를 삭제함에따라 root로부터 leaf까지의 한 경로중에서 black height의 높이가 하나 줄어드는 경로가 발생한다는 것이다.

double black

delete는 insert보다 복잡한 연산이라서 개념 하나가 추가된다. double black이라는 개념이다.

double black은 black 노드x가 삭제되었을때, 그 자리가 x의 black 자식노드로 교체되었을때, 그 자식노드를 double black이라고 말한다.
black자식노드의 왼쪽 subtree들은 모두 black 노드를 하나 잃어버리게 되어 Red-Black트리의 조건을 만족하지 못하게 된다.

delete연산의 핵심은 이 double black노드를 어떻게 single black으로 바꾸는가이다.

로직

1) BST트리의 delete를 수행한다. 2) delete된 노드의 자리를 대체하는 방법은 총 3가지이다

a) delete된 노드가 leaf노드인경우  
b) delete된 노드가 한쪽 자식만 가지는 경우  
c) delete된 노드가 양쪽 자식을 모두 가지는 경우  

c)의 경우, 대체할 노드를 삭제된 노드의 왼쪽서브트리의 최대값이나, 오른쪽 서브트리의 최솟값을 찾아 지우고자하는 노드의 위치로 옮기고, 복사해온 노드를 지운다.
이때, 대체될 이 노드는 반드시 2개보다 적은 non-leaf 자식을 가지고 있다.

왜냐하면, 왼쪽 subtree에서 최대값을 찾든, 오른쪽 subtree에서 최솟값을 찾든, 대체할 노드를 찾았는데 만약 자식이 2개라면 반드시 자기보다 작거나 큰노드가 존재하므로, 그 노드는 대체할 노드가 아니다. (delete할때 원칙을 지키면 반드시 하나 또는 0개의 자식을 가진 노드로 대체한다.)

3) v를 삭제된 노드, u를 v를 대체할 노드라고 가정한다.

4) 단순경우: u또는 v가 red인경우 대체되는 노드 u를 black으로 칠한다.

5) u와 v가 모두 red일수는 없다.

6) u와 v가 모두 black인 경우 u는 double black이 된다. 이제 이 double black을 single black으로 바꿔야한다. v가 leaf였으면 u는 None 노드가되기때문에 이 또한 double black이다.

double black해결

double black이된 sibling 형제노드를 s라고두자. p는 u와 s의 부모이다.

a) s가 black 노드이고, s의 자식 중 적어도 하나가 red인경우, 이 자식을 r이라고 둔다. p와 s, s와 r의 위치에 따라 해야하는 작업이 다르다.

a-1) left-left case는 right-right케이스와 대칭하다. right-right: p기준 left rotation
left-left: p기준 right rotation

a-2) right-left case는 left-right케이스와 대칭하다.

right-left: s기준 right rotation 후 p기준 left rotation
left-right: s기준 left rotation 후 p기준 right rotation

b) s가 black노드일때 s의 자식노드가 모두 black일 경우.

b-1) s의 부모노드 p가 black일 경우 s를 검은색으로 칠하면된다.

그 결과, p를 지나는 모든 경로들은 black을 하나씩 더 적게 가지기때문에 p를 기준으로 rebalancing을 해야한다.

b-2) p가 red인경우, p와 s의 색을 바꾼다.

위의 경우와는 다르게 p를 지나는 노드들이 가지는 black이 일정하게 유지된다.

c) s가 red인경우, p는 당연히 검은색이다. s를 위로 올리고, s와 p의 색을 다시 칠한다.

c-1) s가 p의 right child일때 p와 s의 색을 바꾸고, p를 기준으로 left rotation하면, 새로운 s가 생긴다.
이 새로운 s와 관계에 의해 b-2)를 적용한다.

c-2) s가 p의 left child일때

p와 s의 색을 바꾸고, p를 기준으로 right rotation하면, 새로운 s가 생긴다.
이 새로운 s와 관계에 의해 b-2)를 적용한다.