Red/Black Tree

이진 검색 트리(BST)의 한계

이진 검색 트리(Binary Search Tree, BST)는 효율적인 검색을 위한 자료구조입니다. 하지만 BST에는 치명적인 단점이 있습니다:

• 자료가 많아질수록 트리의 높이가 커질 수 있음
• 최악의 경우, 특정 노드를 탐색하는 데 O(n)의 시간 복잡도가 발생

예를 들어, 1, 2, 3, 4를 순서대로 BST에 추가하면 한쪽으로 치우친 트리가 만들어집니다. 이 경우 4번 노드를 탐색하려면 4번의 비교가 필요합니다.

균형 잡힌 이진 검색 트리의 등장

이러한 BST의 단점을 보완하기 위해 균형 잡힌 이진 검색 트리가 등장했습니다. 이 트리는 노드의 빈번한 추가와 삭제에도 불구하고 트리의 높이를 제한하여 성능상 매우 유리합니다.

균형 잡힌 트리의 장점:

• 불균형한 트리(a) : 루트에서 특정 노드로 갈 때 평균 3.27회의 노드 접근 필요
• 균형 잡힌 트리(b) : 평균 3.0회의 노드 접근으로 감소

Red-Black Tree 소개

Red-Black Tree는 가장 유명하고 널리 사용되는 균형 이진 검색 트리 중 하나입니다.

Red-Black Tree의 5가지 규칙

1. 모든 노드는 빨간색(red) 또는 검은색(black)이어야 합니다.
2. 루트 노드는 항상 검은색입니다.
3. 모든 리프 노드(NIL 노드)는 검은색입니다.
4. 빨간색 노드의 자식은 항상 검은색이어야 합니다. (검은색 노드의 자식은 어떤 색상이어도 됩니다)(RED 노드가 연속적으로 나올 수 없다)
5. 임의의 노드에서 그 노드의 자손인 리프 노드까지 가는 경로들은 모두 같은 수의 검은색 노드를 포함해야 합니다.

Red-Black Tree의 삽입 연산

Red-Black Tree에 새로운 노드를 삽입하는 과정은 다음과 같습니다:

1. 일반적인 BST의 삽입 방식으로 노드를 추가합니다.
2. 새로 삽입된 노드를 빨간색으로 칠합니다.
3. Red-Black Tree의 규칙을 위반했는지 확인합니다.
4. 규칙을 위반했다면 트리를 재조정합니다.

재조정 방법

트리 재조정에는 두 가지 방법이 있습니다:

1. Recoloring: 삽입된 노드의 부모의 형제 노드가 빨간색인 경우
2. Restructuring: 삽입된 노드의 부모의 형제 노드가 검은색이거나 NIL인 경우

Recoloring 예시:

1. 삽입된 노드의 부모와 부모의 형제 노드를 검은색으로 변경
2. 부모의 부모 노드를 빨간색으로 변경
3. 부모의 부모 노드가 루트 노드인 경우, 다시 검은색으로 변경

Restructuring 예시:

1. 삽입된 노드, 부모, 조부모 노드를 오름차순으로 정렬
2. 중간 값을 부모 노드로 만들고 나머지를 자식으로 변환
3. 새로운 부모 노드를 검은색으로, 나머지 노드를 빨간색으로 변경

삽입 과정 예시

Step 1 : Insert 8

• 루트는 흑색인 규칙에 따라 8을 블랙으로 변경됩니다.

Step 2 : Insert 18

Step 3 : Insert 5

Step 4 : Insert 15

• RED 노드가 연속적으로 나올 수 없다 규칙을 위반했다
• 삽입된 노드의 부모와 부모 형제노드를 BLACK으로 부모의 부모노드를 RED로 Recoloring을 해야한다
• 부모의 부모노드가 Root Node인 경우 Root Node인 경우 Black인 규칙에 의해 변경되지 않는다

Step 5 : Insert 17

• RED 노드가 연속적으로 나올 수 없다 규칙을 위반했다
• 삽입된 노드의 부모의 형제 색깔이 NULL이기 때문에 Restructuring을 해야한다
  1. 삽입된 노드, 부모, 부모의 부모(Grand Parent) 오름차순으로 정렬
  2. 중앙 값을 부모 노드로 만들고 나머지 노드를 자식으로 변환
  3. 부모 노드가 된 노드를 BLACK 나머지 노드를 RED로 Recoloring

Step 6 : Insert 25

• RED 노드가 연속적으로 나올 수 없다 규칙을 위반했다
• 삽입된 노드의 부모와 부모 형제노드를 BLACK으로 부모의 부모노드를 RED로 Recoloring을 해야한다

Step 7 : Insert 40

• RED 노드가 연속적으로 나올 수 없다 규칙을 위반했다
• 삽입된 노드의 부모의 형제 색깔이 NULL이기 때문에 Restructuring으로 진행해야 한다
  • 삽입된 노드, 부모, 부모의 부모(Grand Parent) 오름차순으로 정렬
  • 중앙 값을 부모 노드로 만들고 나머지 노드를 자식으로 변환
  • 부모 노드가 된 노드를 BLACK 나머지 노드를 RED로 Recoloring

Step 7 : Insert 80

• RED 노드가 연속적으로 나올 수 없다 규칙을 위반했다
• Recoloring으로 규칙을 위반하지 않게 조정합니다.
• 삽입된 노드의 부모와 부모 형제노드를 BLACK으로 부모의 부모노드를 RED로 Recoloring을 해야한다
• Recoloring이 끝난 이후에 보니 Double Red가 재발생
  • 25 노드의 부모의 형제 색깔이 BLACK이기 때문에 Restructuring으로 진행
    • 삽입된 노드, 부모, 부모의 부모(Grand Parent) 오름차순으로 정렬
    • 중앙 값을 부모 노드로 만들고 나머지 노드를 자식으로 변환
    • 부모 노드가 된 노드를 BLACK 나머지 노드를 RED로 Recoloring