Red Black Tree

Red Black Tree

레드 블랙 트리는 이진 탐색 트리(Binary Search Tree)의 한 종류로
스스로 균형을 잡는(Self-Balancing) 트리로
각각의 노드가 레드나 블랙인 색상 속성을 가지고 있습니다.
대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조 입니다.
시간복잡도는 O(logN) 입니다.

Red Black Tree의 5가지 속성

#1. 모든 노드는 Red 혹은 Black
#2. 루트 노드는 Black
#3. 모든 nil 노드(leaf)는 Black
#4. Red의 자녀는 무조건 Black (Red 연속적으로 존재할 수 없음)
#5. 임의의 노드에서 자손 nil 노드들까지 가는 경로의 Black의 수는 같다

삽입의 규칙

1. 삽입한 노드는 항상 Red (#5 속성 만족)
2. nil 노드색은 Black으로 고정 (#3 속성 만족)
3. 루트노드는 삽입시 Black
4. BST 특징인 자신보다 작은 값들은 왼쪽 큰 값들은 오른쪽 삽입

삽입(Insert)과 회전(Rotate)

삽입시에 구조를 바꾸면서도 BST 특징을 유지 시켜주는 방법중에 회전이 있습니다.

삽입 후 회전 적용하는 케이스 3가지

(괄호) 표시된 것으로 전부 적용하면 반대의 케이스에도 동일하게 적용됩니다.

❗️Case 3

조건

1. 삽입된 노드가 부모의 왼쪽(오른쪽)자녀이며 <Case 3>
2. 부모는 Red이고 할아버지의 왼쪽(오른쪽)자녀이고
3. 삼촌은 Black 인 케이스라면

해결방법

부모와 할아버지의 색상을 변경 후 할아버지 기준으로 오른쪽(왼쪽)으로 회전

❗️Case 2

조건

1. 삽입된 노드가 부모의 오른쪽(왼쪽) 자녀이며 <Case 2>
2. 부모는 Red이고 할아버지의 왼쪽(오른쪽) 자녀이고
3. 삼촌은 Black인 케이스라면

해결방법

부모를 기준 왼쪽(오른쪽)으로 회전한 뒤 Case3 수행

❗️Case 1

조건

1. 삽입된 노드의 부모가 Red이며
2. 삼촌도 Red 인 케이스라면

해결방법

부모와 삼촌을 Black으로 바꾸고 할아버지에서 다시 확인을 시작

삭제의 규칙

1. 삭제하려는 노드의 자녀가 없거나, 1개라면
   삭제 되는색 = 삭제 되는 노드의 색
2. 삭제하려는 노드의 자녀가 2개라면
   삭제되는색 = 삭제되는 노드의 successor의 색
3. 삭제되는 색이 Red라면 어떤 속성도 위반하지 않는다.
4. 삭제되는 색이 Black라면 #2, #4, #5 속성을 위반 하게 됨
   ㄴ 특수 상황을 제외하면 #5번 속성을 항상 위반

Extra Black 역할

삭제되는 색이 Black이고 #5 속성을 위반일때
삭제된 색의 위치에 대체한 노드에 extra black을 부여하여 속성 위반을 해결
경로에서 Black 수를 카운트할때extra black은 하나의 Black으로 카운트

Doubly Black과 Red-and-Black

Doubly Black : extra black이 부여된 대체노드가 Black 노드인 케이스
Red and Black : extra black이 부여된 대체노드가 Red 노드인 케이스

Doubly black 발생 이후에 재조정하는 케이스 4가지

(괄호) 표시된 것으로 전부 적용하면 반대의 케이스에도 동일하게 적용됩니다.

❗️Case 4

조건

1. Doubly black의 오른쪽(왼쪽) 형제가 Black 이며
2. 그 형제의 오른쪽(왼쪽) 자녀는 Red 인 케이스

해결방법

1. 오른쪽(왼쪽) 형제는 부모색(왼쪽)으로,
2. 오른쪽(왼쪽) 형제의 오른쪽(왼쪽) 자녀를 Black으로,
3. 부모는 Black으로 바꾼 후에 부모를 기준으로 왼쪽(오른쪽)으로 회전하여 해결

❗️Case 3

조건

1. Doubly black의 오른쪽(왼쪽) 형제가 Black이며
2. 그 형제의 왼쪽(오른쪽) 자녀가 Red이며
3. 그 형제의 오른쪽(왼쪽) 자녀가 Black일때

해결방법

1. Doubly black의 형제의 오른쪽(왼쪽) 자녀가 Red가 되게 하고
2. 이후에는 Case4 적용

❗️Case 2

조건

1. Doubly black의 형제가 Black이며
2. 그 형제의 두자녀 모두 Black 일때

해결방법

1. Doubly black과 그 형제의 Black을 모아서 부모에게 전달해서
2. 부모가 Extra black 해결을 위임
   ㄴ 부모가 Red-and-black 이면 완료
   ㄴ 부모가 Doubly black 이면서 루트노드이면 Black으로 아니면 Case 1,2,3,4 로 해결

❗️Case 1

조건

1. 오른쪽(왼쪽) Doubly Black 형제가 Red 일때

해결방법

1. Doubly black의 부모와 형제의 색을 바꾸고
2. Doubly black의 부모를 기준으로 왼쪽(오른쪽)으로 회전한 뒤
   Doubly black을 기준으로 Case 2,3,4로 해결

---

참고자료

• 쉬운코드(Youtube)
• Introduction to Algorithms