Red-Black Tree

레드-블랙 트리(Red-Black Tree)

 

 

레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다.

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

삽입

우리는 삽입 후 밸런싱을 하기 위해 회전을 도구로 사용했습니다. Red-Black 트리에서 우리는 밸런싱을 하기 위해 두 가지 도구를 사용합니다. 

1. Recoloring
2. Rotation

트리 Rotation은 요소의 순서를 방해하지 않고 구조를 변경하는 이진 트리 의 연산입니다 . 트리 Rotation 은 트리에서 한 노드를 위로, 한 노드를 아래로 이동합니다. 트리의 모양을 변경하는 데 사용되며, 특히 작은 서브트리를 아래로, 큰 서브트리를 위로 이동하여 트리의 높이를 줄이는 데 사용되어 많은 트리 연산의 성능이 향상됩니다

Recoloring은 노드의 색상을 바꾸는 것입니다. 즉, 빨간색이면 검은색으로 바꾸고 그 반대도 마찬가지입니다. NULL 노드의 색상은 항상 검은색이라는 점에 유의해야 합니다. 게다가 항상 재색칠을 먼저 시도하고, 재색칠이 작동하지 않으면 회전을 시도합니다. 자세한 알고리즘은 다음과 같습니다. 알고리즘은 삼촌 노드의 색상에 따라 주로 두 가지 경우가 있습니다. 삼촌 노드가 빨간색이면 Recoloring을 합니다. 삼촌 노드가 검은색이면 Rotation 또는 Recoloring 을 합니다.

로직

먼저, 이진 트리에 노드를 삽입하는 것과 비슷하게 삽입하고 빨간색으로 지정해야 합니다. 이제 노드가 루트 노드인 경우 색상을 검은색으로 변경하지만 그렇지 않은 경우 부모 노드의 색상을 확인합니다. 색상이 검은색인 경우 색상을 변경하지 않지만 그렇지 않은 경우(즉, 빨간색인 경우) 노드의 삼촌의 색상을 확인합니다. 노드의 삼촌이 빨간색인 경우 노드의 부모와 삼촌의 색상을 검은색으로 변경하고 할아버지의 색상을 빨간색으로 변경한 다음 그에게(즉, 할아버지) 동일한 프로세스를 반복합니다. 할아버지가 루트인 경우 할아버지를 빨간색으로 변경하지 않습니다.

하지만 노드의 삼촌이 검은색이라면 4가지 가능한 경우가 있습니다.

• 왼쪽 왼쪽 케이스(LL 회전):

• 왼쪽 오른쪽 케이스(LR 회전):

• 오른쪽 오른쪽 케이스(RR 회전):

• 오른쪽 왼쪽 케이스(RL 회전):

이제 이러한 회전을 거친 후, 회전 사례에 따라 다시 색상을 지정합니다

연산:

x를 새로 삽입된 노드라고 하자.

1. 표준 BST 삽입을 수행 하고 새로 삽입된 노드의 색상을 빨간색으로 지정합니다.
2. x가 루트이면, x의 색상을 검은색으로 변경합니다. (완전한 트리의 검은색 높이는 1만큼 증가합니다.)
3. x의 부모의 색상이 BLACK이 아니고 x가 루트가 아닌 경우 다음을 수행합니다 .a ) 
   x의 삼촌이 RED 인 경우(조부모는 속성 4 에서 검은색이어야 함 )  (i) 부모와 삼촌의 색상을 BLACK으로 변경합니다.  (ii) 조부모의 색상을 RED로 변경합니다.  (iii) x = x의 조부모로 변경하고 새 x에 대해 2단계와 3단계를 반복합니다.b  ) x의 삼촌이 BLACK인 경우 x에 대해 네 가지 구성이 있을 수 있습니다.x의 부모( p )와 x의 조부모( g ) (이는 AVL 트리 와 유사함 )  (i) 왼쪽 왼쪽 케이스(p는 g의 왼쪽 자식이고 x는 p의 왼쪽 자식)  (ii) 왼쪽 오른쪽 케이스(p는 g의 왼쪽 자식이고 x는 p의 오른쪽 자식)  (iii) 오른쪽 오른쪽 케이스(케이스 i의 미러)  (iv) 오른쪽 왼쪽 케이스(케이스 ii의 미러)
   

회전 후 재색칠 :
Left Left Case [3.b (i)] 및 Right Right Case [3.b (iii)]의 경우 회전 후 조부모와 부모 노드의 색상을 바꿉니다.
Left Right Case [3.b (ii)] 및 Right Left Case [3.b (iv)]의 경우 회전 후 조부모와 삽입된 노드의 색상을 바꿉니다.

 

예: 빈 트리에 3, 21, 32, 15라는 요소를 포함하는 빨간색-검은색 트리를 만듭니다.

해결책: 

첫 번째 요소가 삽입될 때 루트 노드로 삽입되고 루트 노드는 검은색이므로 검은색이 됩니다.

 

새로운 요소는 항상 빨간색으로 삽입되고, 21 > 3이므로 루트 노드의 오른쪽 서브 트리의 일부가 됩니다. 

 

이제 32를 삽입하면 Red-Black 트리 규칙을 위반하는 빨간색 아버지-자식 쌍이 있으므로 회전해야 합니다. 게다가 RR 회전의 조건(루트 노드의 널 노드를 검은색으로 간주)을 확인하므로 회전 후 루트 노드가 빨간색이 될 수 없으므로 트리에서 다시 색칠해야 위에 표시된 트리가 생성됩니다. 

 

최종 트리 구조: 

삭제

적색-흑색 트리에서 노드를 삭제하는 과정

1. 삭제할 노드에 자식 노드가 없으면, 해당 노드를 제거하고 부모 노드를 업데이트하기만 하면 됩니다.
2. 삭제할 노드에 자식이 하나만 있는 경우, 해당 노드를 자식 노드로 교체합니다.
3. 삭제할 노드에 자식이 두 개 있는 경우, 해당 노드를 오른쪽 서브트리의 가장 왼쪽 노드인 inorder successor로 교체합니다. 그런 다음 최대 자식이 하나뿐인 것처럼 inorder successor 노드를 삭제합니다.
4. 노드가 삭제된 후, 레드-블랙 속성이 위반될 수 있습니다. 이러한 속성을 복원하기 위해 트리의 노드에서 일부 색상 변경 및 회전이 수행됩니다. 변경은 삽입 중에 수행된 변경과 유사하지만 조건이 다릅니다.
5. 적색-흑색 트리의 삭제 작업은 평균적으로 O(log n) 시간이 걸리므로 대규모 데이터 세트에서 요소를 검색하고 삭제하는 데 적합한 선택입니다.

삽입 대 ​​삭제: 삽입과 마찬가지로, Recoloring과 Rotaion은 Red-Black 속성을 유지하는 데 사용됩니다. 삽입 작업에서 삼촌의 색상을 확인하여 적절한 경우를 결정합니다.삭제 작업에서 형제의 색상을 확인하여 적절한 경우를 결정합니다. 삽입 후에 위반되는 주요 속성은 두 개의 연속된 빨간색입니다.삭제에서 위반되는 주요 속성은 서브 트리에서 검정색 높이가 변경되는 것입니다.검정색 노드를 삭제하면 한 루트에서 리프 경로로의 검정색 높이가 줄어들 수 있습니다. 삭제는 상당히 복잡한 프로세스입니다.삭제를 이해하기 위해 이중 검정색이라는 개념이 사용됩니다.검정색 노드가 삭제되고 검정색 자식으로 바뀌면 자식은 이중 검정색 으로 표시됩니다 .이제 주요 작업은 이 이중 검정색을 단일 검정색으로 변환하는 것입니다. 삭제 단계 다음은 삭제에 대한 자세한 단계입니다.1 ) 표준 BST 삭제를 수행합니다 . BST에서 표준 삭제 작업을 수행할 때 항상 리프 노드이거나 자식이 하나만 있는 노드를 삭제하게 됩니다(내부 노드의 경우 후속 노드를 복사한 다음 후속 노드에 대해 재귀적으로 삭제를 호출합니다. 후속 노드는 항상 리프 노드이거나 자식이 하나인 노드입니다). 따라서 노드가 리프이거나 자식이 하나인 경우만 처리하면 됩니다. 삭제할 노드를 v로 하고 v를 대체하는 자식을 u로 합니다(v가 리프이고 NULL의 색상이 검은색으로 간주될 때 u는 NULL임에 유의하세요). 2) 간단한 경우: u 또는 v가 빨간색이면 대체된 자식을 검은색으로 표시합니다(검정색 높이 변경 없음). u와 v가 모두 빨간색일 수 없는 데, v가 u의 부모이고 빨간색-검정색 트리에서는 두 개의 연속된 빨간색이 허용되지 않기 때문입니다.  

3) u와 v가 모두 검은색이면 .
3.1) u를 더블 블랙으로 채색합니다. 이제 우리의 과제는 이 더블 블랙을 싱글 블랙으로 변환하는 것으로 축소됩니다. v가 잎이면 u가 NULL이고 NULL의 색상은 검은색으로 간주됩니다. 따라서 검은색 잎을 삭제하면 더블 블랙이 발생합니다.
 

3.2) 현재 노드 u가 더블 블랙이고 루트가 아닐 때 다음을 수행합니다. 노드의 형제 노드를 s 라고 합니다 . 
…. (a): 형제 노드 s가 블랙이고 형제 노드의 자식 중 하나 이상이 레드인 경우 회전을 수행합니다. s의 레드 자식 노드를 r이라고 합니다 . 이 경우는 s와 r의 위치에 따라 네 가지 하위 경우로 나눌 수 있습니다.
………….. (i) 왼쪽 왼쪽 케이스(s가 부모 노드의 왼쪽 자식이고 r이 s의 왼쪽 자식이거나 s의 두 자식이 모두 레드인 경우). 이것은 아래 다이어그램에 표시된 오른쪽 오른쪽 케이스의 미러입니다.
………….. (ii) 왼쪽 오른쪽 케이스(s가 부모 노드의 왼쪽 자식이고 r이 오른쪽 자식인 경우). 이것은 아래 다이어그램에 표시된 오른쪽 왼쪽 케이스의 미러입니다.
………….. (iii) 오른쪽 오른쪽 케이스(s가 부모 노드의 오른쪽 자식이고 r이 s의 오른쪽 자식이거나 s의 두 자식이 모두 레드인 경우) 
 

………….. (iv) 오른쪽 왼쪽 케이스 (s는 부모의 오른쪽 자식이고 r은 s의 왼쪽 자식) 
 

….. (b): 형제가 검은색이고 그 자식이 둘 다 검은색이면 다시 색칠하고, 부모가 검은색이면 부모에 대해 재귀합니다. 
 

이 경우, 부모가 빨간색이면 부모에 대해 재귀할 필요가 없고, 간단히 검은색으로 만들 수 있습니다(빨간색 + 두 개의 검은색 = 하나의 검은색)
….. (c): 형제가 빨간색이면 회전을 수행하여 이전 형제를 위로 이동하고 이전 형제와 부모를 다시 칠합니다. 새로운 형제는 항상 검은색입니다(아래 다이어그램 참조). 이는 주로 트리를 검은색 형제 케이스(회전에 의해)로 변환하고 케이스 (a) 또는 (b)로 이어집니다. 이 케이스는 두 개의 하위 케이스로 나눌 수 있습니다. 
………….. (i) 왼쪽 케이스(s가 부모의 왼쪽 자식). 이것은 아래 다이어그램에 표시된 오른쪽 오른쪽 케이스의 미러입니다. 부모 p를 오른쪽으로 회전합니다. 
………….. (ii) 오른쪽 케이스(s가 부모의 오른쪽 자식). 부모 p를 왼쪽으로 회전합니다. 
 

3.3) u가 루트이면, 그것을 단일 블랙으로 만들고 (완전한 트리의 블랙 높이가 1만큼 감소함)을 반환합니다.