Red-black tree

시작은 역시 link로

 

Red–black tree - Wikipedia

 

 

학교에서 알고리즘 스터디를 진행하고 있다. 매주마다 어떤 것을 다룰 것인지 고민하다 set, map에 생각이 미쳤고 (사실 다룰 것 같지는 않지만) set, map의 기반이라 볼 수 있는 red-black tree를 다시 보게 되었다.

 

 

tree의 구조를 살펴보면 왜 red-black tree인지 알 수 있다.

 

C++의 경우 set과 map은 red-black tree로, unordered_set과 unordered_map은 hash table로 구현되어 있다.

 

당연하게도 unordered_set과 unordered_map이 더 빠른 속도를 가지지만 hash를 사용하기 때문에 안정성이 부족하다. 따라서 set, map을 사용하는 것이 좋다. (코포에서는 hash collison이 유발되는 input으로 hack을 넣기도 한다더라)

 

 

먼저 Red-black tree는 self-balancing binary search tree의 일종이다. (따라서 각 node에 대해 왼쪽 subtree의 node들은 자신보다 작고 오른쪽 subtree의 node들은 자신보다 큰 수를 가진다.)

 

 

Red-black tree는 다음과 같은 성질을 갖는다.

 

1. Every node is either red or black
2. The root and leaves(NIL) are considered black.
3. A red node does not have a red child. (If a node is red, its children are black.)
4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

 

성질 4는 다음과 같은 명제를 참이 되도록 만든다.

• \( h(v) \): \( v \)의 높이
• \( bh(v) \): \( v \)에서 descendant NIL nodes로 가는 path에 포함되는 black node의 개수 (자기 자신 배제)
• | v의 subtree | \( \geq \) \( 2^{bh(v)} - 1 \)

이는 간단히 귀납법으로 증명이 가능하다.

 

 

또한 다음 명제는 성질 3 덕에 당연히 참이다.

• \( bh(v) \geq \frac{h(v)}{2} \)

 

둘을 결합한 결과는 tree의 높이를 \( \log n \)으로 제한한다.

• r: root node
• | red-black tree | = \( n \geq 2^{bh(r)} - 1 \geq 2^{\frac{h(r)}{2}} - 1 \)
• 따라서 \( h(r) \leq 2 \log{(n + 1)} \)

 

위의 증명 과정을 잘 설명하셨다

 

Red-black tree의 높이가 \( \log n \) 로 bounding 되는 것을 알게 되었고 이로 인해 tree안의 특정 element로의 접근이 \( \log n \)만에 가능하다는 것을 알 수 있다. (search: \( \log n \))

 

그렇다면 red-black tree의 특성들을 유지하며 insertion, deletion을 어떻게 수행할 수 있을까.

 

 

그 전에 rotation부터 알아보자.

 

Rotation은 tree structure를 재배열하여 tree의 높이를 줄이는 것이 목적인 operation이다.

(그렇다기에는 예시에서는 딱히 높이의 변화가 없다.)

간단하다.

 

 

Insertion은 네 가지 경우에 따라 수행하는 절차가 달라진다.

 

본격적으로 insertion part에 들어가기 전 알아둬야 할 terminology

 

먼저 node z를 BST 성질을 만족하도록 tree에 삽입한 다음 red로 칠해주자.

 

• Case 0: The node z is root
  • Property 1을 위해 z를 black으로 칠해준다.
• Case 1: z.uncle = red
  • z.parent, z.grandparent, z.uncle을 recolor 해준다. (red-black tree의 property를 violation 하지 않도록)
• Case 2: z.uncle = black (triangle)
  • 여기서 triangle이란 z가 z.parent의 left child이고 z.parent가 z.grandparent의 right child일 때, 혹은 z가 z.parent의 right child이고 z.parent가 z.grandparent의 left child일 때를 의미한다.
  • z.parent를 rotation 시켜준다.

여기서는 right-rotation

• Case 3: z.uncle = black (line)
  • z.uncle이 black일 때, case 2 외의 경우
  • z.grandparent를 z 반대방향으로 rotation 시켜준다.
  • 그런 다음 parent와 grandparent를 recolor 해주어야 한다.

여기서는 left-rotation

 

노드를 삽입한 후에 거치는 과정이 재귀적으로 위로 올라가며 노드 z를 선택하여 constant time(recoloring)으로 실행되므로 insertion의 time complexity는 \( O(\log n) \)이 된다.

 

RB-tree insertion pseudo code

설명 너무 잘하심

 

 

영상에서는 deletion을 위한 세 가지 operation을 제시한다.

 

 

Transplant

 

 

- helps us move subtrees within the red-black tree

 

Transplant

v로 u를 대체한다. 이 때 u의 children에 대해서는 transparent를 call한 calling function이 처리할 것이다.

 

 

Delete

 

 

세 가지 case를 고려해야한다.

 

1. Left child is NIL.

2. Right child is NIL.

3. Neither child is NIL.

 

case 1, 2의 경우 NIL 반대 쪽 child와 삭제하려는 노드를 transplant 한다.

case 3의 경우 삭제하려는 노드 A의 오른쪽 subtree에서 가장 작은 노드 B를 찾아 B와 B의 right child를 transplant 시키고 A와 B를 transplant 한다.

 

삭제하려는 노드를 성공적으로 지웠다. 이제는 red-black tree의 특성을 가지도록 coloring 해줘야한다.

 

 

 

Delete Fixup

 

 

네 가지 case를 고려해야 한다. 여기서 w는 x의 sibling이다.

 

1. w is red

2. w is black, and w.left & w.right are black

3. w is black, and w.left is red and w.right is black

4. w is black, and w.right is red

 

 

원하는 노드를 삭제한 뒤 delete_fixes로 red-black tree의 특성들을 강제할 수 있다.

 

이게 왜 가능한지는 case를 나누어 살펴봐야할 것 같아 스킵.