균형 이진 탐색 트리 - Red-Black Tree

📒 Red-Black Tree

📌 Red-Black Tree란?

• 레드-블랙 트리는 정렬된 정보를 빠르게 탐색 및 저장하고 알려진 시간 내에 작업이 완료되도록 보장하는 특수한 이진 탐색 트리 구조이다. (균형 이진 탐색 트리)
• 다른 자체 균형 이진 트리와 비교하여 레드-블랙 트리의 노드는 "빨간색"과 "검은색"을 나타내는 "색상"이라는 추가 비트를 보유하며, 이는 트리를 재구성할 때 항상 대략적인 균형을 맞추기 위해 사용된다.
• 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도를 갖는다.
  
  

📌 Red-Black Tree의 특징

• 트리가 수정되면 새 트리가 재배열되고 "repainted"되어, 최악의 경우 트리의 불균형을 제한하는 색상 속성을 설정한다.
• 재배열 및 repainted 작업을 효율적으로 실행할 수 있도록 설계되어 있다.
• (재)밸런싱은 완벽하지는 않지만, O(log n)의 시간을 보장한다.
• 삽입 및 삭제는 트리 재배열 및 repainted와 함께 수행된다. O(log n)
• 두 가지 색상만 있기 때문에 각 노드의 색상을 추적하려면 노드당 1비트의 정보만 필요하다.
• 트리에는 레드-블랙 트리와 관련된 다른 데이터가 포함되어 있지 않으므로 메모리 공간은 이진 탐색 트리의 메모리 공간과 거의 동일하다.
• (루트 노드 ~ 가장 먼 리프 노드) < (루트 노드 ~ 가장 가까운 리프 노드) * 2
  
  

📌 Red-Black Tree 예시

출처 : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties

📌 Red-Black Tree의 규칙

1. 모든 노드는 레드이거나 블랙이다.
2. 루트 노드는 블랙이다.
3. 노드가 레드면 두 자식 모두 블랙이다.
4. 특정 노드에서 리프 노드(NIL)까지의 모든 경로는 동일한 수의 블랙 노드를 통과한다.
5. 모든 리프 노드(NIL)는 블랙이다.
   NIL : 자식 노드가 존재하지 않는 경우 NIL 노드라는 특수한 노드가 있다고 생각한다.
   따라서 모든 리프 노드는 NIL 노드가 된다. 또한 루트의 부모도 NIL 노드라고 생각하자.
   
   

📌 Red-Black Tree를 사용하는 이유

• C++ STL의 map, multimap, set, multiset이 red-black tree로 구현되어 있다.
• 만약, 일반 BST(이진 탐색 트리)를 사용한다고 가정하자.
• BST는 노드의 왼쪽 하위 트리에는 노드의 값보다 작은 값이 존재하고, 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 존재하는 구조이다.
• 따라서 BST는 검색하기에 용이한 구조이고 평균적으로 O(log n)의 시간 복잡도를 갖는다.
• 그러나 최악의 경우(ex. 1 -> 2 -> 3 -> 4 순으로 삽입하는 경우) 트리가 선형적인 구조가 될 수 있고, 이때의 시간 복잡도는 O(N)이다.
• 이처럼 BST는 삽입 순서에 따라 트리의 형태가 불리해질 수 있기 때문에 O(log n)의 시간을 보장해 주지 못한다.
• 항상 높이가 log n임이 보장된다면 최악의 상황에도 O(log n)의 속도를 보장할 수 있다.
• 이 때문에 red-black tree는 "색상"이라는 추가 비트를 통해 트리의 높이를 항상 log n으로 보장해 주기 때문에 사용하는 것이다.
  
  

📌 Red-Black Tree 탐색

• 현재 노드가 찾는 값이면 return
• 현재 노드가 찾는 값보다 크다면 왼쪽
• 현재 노드가 찾는 값보다 작다면 오른쪽
  
  

📌 Red-Black Tree 삽입

1. 새로운 원소를 삽입하고 이 노드를 레드로 지정한다. (검은색으로 지정하게 되면 규칙 4를 위반할 위험이 있음)
2. 다음 노드를 삽입할 때, 규칙 3을 위반할 수 있기 때문에 (재)밸런싱 작업이 필요하다.

Recoloring

• 리컬러링은 삽입된 노드의 삼촌 노드(부모 노드의 형제 노드)의 색상이 레드일 때 발생한다.
• 먼저, 새로운 노드를 추가하고(이하 x) x가 루트 노드이면 블랙으로 변경, 그렇지 않으면 상위 노드의 색상을 확인한다.
• 만약 상위 노드의 색상이 블랙이면 변경하지 않고, 레드라면 x의 삼촌 노드의 색상을 확인한다.
• 삼촌 노드가 레드인 경우, x의 부모와 삼촌 노드는 블랙으로 할아버지 노드는 레드로 변경한다.
• 이때, 할아버지 노드가 루트 노드라면 블랙으로 변경한 후 종료하고, 만약 할아버지의 아버지 노드가 레드라면 레드 노드끼리는 인접할 수 없기 때문에 할아버지 노드에 대해 동일한 과정을 반복해야 한다.

Rotation

• 로테이션은 리커러링과 반대로 새로운 노드의 삼촌 노드가 블랙일 때 수행한다.
• 로테이션은 Left Rotate와 Right Rotate로 나뉜다.
  Left Rotate : 현재 노드와 왼쪽 자식 노드의 위치를 변경한다.
  RBT는 BST이기 때문에 이 둘의 위치를 함부로 바꾸면 왼쪽 자식은 루트 노드보다 작아야 한다는 BST의 원칙을 위반하게 된다. 따라서, 이들이 포함된 서브 트리 전체를 회전시켜 주어야 한다.
  Right Rotate : 현재 노드와 오른쪽 자식 노드의 위치를 변경하고 BST의 원칙을 준수할 수 있도록 나머지 노드들도 조정해 주어야 한다.
  
  

📌 Red-Black Tree 삭제

• RBT의 삭제는 BST의 삭제에 기반한다.
• 노드를 삭제하고 나면, 무너진 RBT의 규칙을 복원하는 것에 초점을 둔다.

레드 노드가 삭제된 경우

• 이 경우에는 어떠한 추가 작업도 필요하지 않다.
• 규칙이 무너지는 경우는 레드 노드가 연속적으로 부모 자식 관계인 경우인데, 레드가 삭제된다고 해서, 규칙이 무너지지 않기 때문이다.

블랙 노드가 삭제된 경우

• Case Default : 삭제가 일어나면 무조건 실행이 되는 케이스
  • 삭제된 노드가 블랙인 경우, 그 자리를 대체하는 노드를 블랙으로 변경한다.
  • 만약, 그 자리를 대체한 노드가 원래 블랙인 경우, 원래 블랙이었던 노드를 다시 블랙으로 칠하게 되는 경우가 발생하는데, 이를 "이중 흑색 노드"라 한다.
  • 이중 흑색 노드를 해결하려면 케이스 별로 처리 방식이 다르다.

이중 흑색 노드인 경우

• Case Change : 삭제할 타깃(이하 x)의 형제 노드가 레드인 경우
  • x의 형제 노드를 블랙으로 변경
  • 부모를 레드로 변경
  • 부모 노드를 기준으로 Left Rotate
• Case 1 : x의 형제가 블랙, 형제의 자식이 모두 블랙인 경우
  • 형제 노드만 레드로 변경
  • 이중 흑색 노드의 검은색을 부모에게 전달
  • 부모가 레드였다면 블랙으로 변경하고 끝날 테지만, 부모가 블랙인 경우 다시 이중 흑색 노드가 되고 만다.
  • 따라서 부모가 이중 흑색 노드가 된 경우, 그 부모를 타깃으로 하여 Case 상황을 거쳐 (재)밸런싱을 해나가야 한다.
• Case 2 : x의 형제가 블랙, 형제의 왼쪽 자식이 레드, 오른쪽 자식이 블랙인 경우
  • 형제 노드를 레드로 변경
  • 형제 노드의 왼쪽 자식을 블랙으로 변경
  • 형제 노드를 기준으로 Right Rotate
• Case 3 : 이중 흑색 노드의 형제가 블랙, 형제의 오른쪽 자식이 레드인 경우
  • 부모 노드의 색을 형제에게 전달
  • 부모 노드와 형제 노드의 오른쪽 자식을 블랙으로 변경
  • 부모 노드 기준으로 Left Rotate