자료구조 - [ Red-Black 트리 ]

Red-Black 트리

Red-Black 트리는 AVL 트리와 비슷하게 스스로 균형 잡는 이진 탐색 트리로, 삽입/삭제 시 노드가 가지고 있는 색깔을 이용한 규칙을 통해 불균형을 완화하는 트리이다.

 

노드의 재배치를 빈번하게 실행하지 않기 때문에 삽입/삭제 연산이 많은 경우 AVL 트리보다 평균적으로 더 나은 성능을 가지고 있고, AVL 트리보다 덜 균형하기 때문에 탐색 횟수는 더 많을 수 있다.

=> 삽입/삭제 연산이 빈번하면 Red-Black 트리  /  탐색의 성능이 더 중요한 경우 AVL 트리를 이용하는 것이 낫다.

 

 

• 모든 노드는 빨강 또는 검정
• 루트 노드는 최종적으로 항상 검정
• 모든 Leaf 노드는 루트 노드와 동일한 색상을 가짐
• 모든 빨강 노드의 자식은 검정 노드(검정 노드의 자식은 상관 X) => 빨강 노드의 자식 노드로 빨강 노드가 오면 재배치 실행
• 하나의 노드에서 후손 노드로 가는 모든 단순 경로에는 동일한 수의 검정색 노드가 존재

 

 

---

Red-Black 트리 삽입

1. 삽입 시 이진 탐색 트리의 규칙에 의해 노드의 위치가 정해지며 빨강 노드로 삽입된다.
2. 삽입된 위치에서 부모 노드가 빨강 노드인 경우 (=Double Red인 경우) 재배치를 실행한다. 
3. 루트 노드인 경우 해당 노드를 검정색으로 변경한다.

 

 

---

노드가 재배치되는 상황 4가지

1. 삼촌 Red, 우측-우측 Double Red   =>  Recoloring

< 재배치 >

1. 조부모 노드(g)의 색깔을 빨강으로 변경

2. 삼촌 노드(u)와 부모 노드(p)의 색깔을 검정으로 변경

 

 

---

2. 삼촌 Red, 우측-좌측 Double Red  =>  Recoloring

< 재배치 >

1. 조부모 노드(g)의 색깔을 빨강으로 변경

2. 삼촌 노드(u)와 부모 노드(p)의 색깔을 검정으로 변경

 

 

---

3. 삼촌 Black, 우측-우측 Double Red  =>  Restrucutring

< 재배치 >

1. 조부모 노드(g)와 부모 노드(p)의 색깔을 swap

2. 부모 노드(p)를 축으로 Left-Rotation 실행 (=AVL 트리의 RR회전)

 

---

4. 삼촌 Black, 우측-좌측 Double Red  =>  Restructuring

 

< 재배치 >

1. 부모 노드(p)를 축으로 Right-Rotation 실행 (= AVL 트리의 LL 회전)

2. 조부모 노드(g)와 새로운 부모 노드의 색깔을 Swap

3. 새로운 부모 노드를 축으로 Left-Rotation 실행 (= AVL 트리의 RR 회전)

 

 

---

Red-Black 트리 삭제

빨강 노드는 삭제되더라도 '주어진 노드에서 후손 노드로 가는 모든 단순 경로에는 동일한 수의 검은색 노드가 존재' 규칙에 위배되지 않는다.

그러나 검정 노드가 삭제될 경우 전체 트리 관점에서 경로상 검정 노드의 개수가 불일치 하는 상황이 발생할 수 있다. 이 부분을 조정하기 위해 노드의 재배치를 실행해야 한다.

 

검정 노드를 삭제할 시 트리의 상황은 네 가지이다.

1. 삭제할 노드의 형제 노드가 빨강 노드
2. 삭제할 노드의 형제 노드의 자식 색깔이 모두 검은색
3. 삭제할 노드의 형제 노드의 좌측 자식 색깔이 빨강, 우측 자식은 검정
4. 삭제할 노드의 형제 노드의 우측 자식이 빨강, 좌측 좌식 색깔은 상관 없음

=> Case2 : 우측 서브 트리의 경로상 검정 노드 개수를 줄인다.

=> Case1, 3, 4 : 좌측 서브 트리의 경로상 검정 노드 개수를 늘린다.

 

 

---

Case 1. 삭제할 노드의 형제 노드가 빨강 노드

 

---

Case 2. 삭제할 노드의 형제 노드의 자식 색깔이 모두 검은색

 

---

Case 3. 삭제할 노드의 형제 노드의 좌측 자식 색깔이 빨강, 우측 자식이 검정

 

---

Case 4. 삭제할 노드의 형제 노드의 우측 자식이 빨강, 좌측 자식 색깔은 상관 없음

 

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼