[SW 정글 26일차] Red-Black tree (#삽입)

RB tree는 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 종류로, 검색, 삽입, 삭제 등의 동작을 최악의 경우에도 O(log n) 내에 처리할 수 있도록 설계되었다. RB tree는 각 노드가 빨강 또는 검정의 색깔을 가지며, root부터 leaf(NIL)까지의 모든 경로에 대해 블랙 노드의 수가 동일하게 유지되도록 규칙을 적용하여 균형을 맞춘다. RB tree를 사용하는 이유는 데이터의 삽입, 삭제, 검색 작업 시 '항상 균형 상태를 유지'함으로써, 트리의 높이가 최소한으로 유지되어 효율적인 시간 복잡도를 보장한다.

Binary Search Tree란,

1. 정렬된(ordered, or sorted) binary tree이며
2. 노드는 2개의 서브트리를 가질 수 있음
3. 특정 노드의 왼쪽에 있는 항목이 오른쪽에 있는 항목보다 더 작음

Example

BST

간단한 구조의 BST이다. 다만 최상단의 root node에서 한 쪽(왼쪽 또는 오른쪽)으로 노드가 쏠려 있으면 어떻게 될까? 최악의 경우 모든 노드를 탐색하여야 원하는 노드를 찾을 수 있다.

이런 비효율을 해결한 Search Tree가 Balanced Search Tree이다.

Balanced Search Tree

이는 n개의 노드를 탐색 시 O(log n) time complexity를 guarantee 한다.

Red - Black Tree(RB Tree)

RB Tree는 Balanced Search Tree의 특정 유형 중 하나이다.

 

RB Tree의 기준(criteria)

1. 노드는 Red or Black
2. 루트(root)와 잎(leaves(NIL))은 Black
3. 노드가 Red라면 children은 Black
4. 모든 nodes to NIL paths에는 같은 수의 Black node를 가짐

+

1. Nodes는 색상을 트래킹하기 위한 bit storage가 필요함
2. 가장 긴 path(root to farthest NIL)는 가장 짧은 path(root to nearest NIL)의 두 배보다 길 수 없다.
   • 가장 짧은 path는 모두 Black nodes
   • 가장 긴 path는 Red, Black 함께 존재

RB Tree's Operation

• Search
  • time complexity : O(log n)
• Insert
  • time complexity : O(log n)
  • RB Tree properties violation 시 rotaion 기법 필요
• Remove
  • time complexity : O(log n)
  • RB Tree properties violation 시 rotaion 기법 필요

삽입(Insertions)

RB Tree는 Self-balancing Binary Search Tree이므로 새로운 노드를 삽입할 때 트리가 조정되면서 RB Tree 속성이 충족되는지 확인해야 한다.

삽입 시 RB Tree properties를 유지하기 위해 사용되는 기법 중 rotate는 다음과 같다.

*Rotation

1. subtress를 재배열(rearranging)하여 tree 구조를 바꾸는 것
2. 목표는 tree의 height를 낮추기 위함!
   • RB Tree : 최대 height 수준은 O(log n)
   • height가 높은 subtrees는 올림, 낮은 subtrees는 내림
3. elements의 순서에 영향을 주지는 않음(여전히 작은 수가 왼쪽에, 큰 수가 오른쪽에 위치함)

Right rotation example

• 트리의 포인터를 바꾸는 것만으로 rotation이 가능하기에 time complexity는 O(1)

삽입 전략

1. Red Z node 삽입
2. Fix Violation(recolor and rotate nodes)

4가지 주요 시나리오

1. Z = root
2. Z.uncle = red
3. Z.uncle = black(triangle)
4. Z.uncle = black(line)

✔️ Z = root

Z는 삽입되는 노드를 뜻한다.

이 Case는 삽입되는 노드가 root가 되는 것이다. RB Tree 속성에 맞게 Red → Black으로 recolor만 하면 된다.

 

✔️ Z.uncle = red

Fix 후 결과 이미지(B node가 Red인 것은 subtree 중 하나이기 때문)

삽입되는 노드의 uncle(= Z.uncle)의 color가 red일 때, Z.uncle과 Z.grandparent의 color를 swap 하여 Fix 한다.

 

swap 후 violation을 일으키는 노드가 Z가 되며 시나리오를 체크한다.

 

✔️ Z.uncle = black(triangle)

해당 Case의 subtree 예시

Z.uncle의 color가 black이고, Z.parent가 Z.grandparent의 right이라면, Z가 Z.parent의 left일 때, Z.parent를 RightRotate 한다.

역으로 Z.uncle의 color가 black이고, Z.parent가 Z.grandparent의 left이라면, Z가 Z.parent의 right일 때, Z.parent를 LeftRotate 한다.

Rotate 후 violation을 일으키는 노드가 Z가 되며 시나리오를 체크한다.

✔️ Z.uncle = black(line)

해당 케이스의 subtree 예시

Z.uncle의 color가 black이고, Z.parent가 Z.grandparent의 right이라면, Z가 Z.parent의 right일 때, Z.parent를 LeftRotate 한다.

역으로 Z.uncle의 color가 black이고, Z.parent가 Z.grandparent의 left이라면, Z가 Z.parent의 left일 때, Z.parent를 RightRotate 한다.

Rotate 후 violation을 일으키는 노드가 Z가 되며 시나리오를 체크한다.

 

위 시나리오를 거친 후 RB Tree properties를 만족시킬 경우 삽입 완료가 된다.

📝 sudo Code

RB Tree 삽입에 대한 sudo code