[자료구조] Red-Black Tree

Red-Black Tree

정의

Self-balanced Binary Search Tree의 종류로 모든 노드가 빨간색과 검정색으로 표현 된다.

노드에 대한 정의

G : 조상 노드

P : 부모 노드

U : 삼촌 노드 (부모 노드의 형제)

N : 새로 삽입한 노드 (자식)

균형 유지의 조건

1. 모든 노드는 빨간색 또는 검은색이어야 한다
2. 루트 노드는 검은색이다
3. 모든 NIL은 검은색이다 (NIL: Null Leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드)
   • NIL 노드는 값이 있는 노드와 동등하게 취급한다
4. 빨간색 노드의 자식은 반드시 검은색이다
5. 임의의 노드에서 자손 NIL 노드까지 가는 경로의 black 수는 같다 (단, 자기 자신은 카운트 제외)
   • 노드 x의 Black height : x에서 임의의 자손 nil노드까지 내려가는 경로에서의 black 수
   • 5 속성을 만족할 때, 두 자녀가 같은 색을 가지면 부모와 두 자녀의 색을 바꾸더라도 속성은 여전히 만족한다. → 삽입 삭제 시 유용하게 쓴다.

R-B 트리의 특성

1. 루트 노드부터 가장 먼 리프 노드 경로까지의 거리가, 가장 가까운 리프 노드 경로까지의 거리의 두 배 보다 항상 작다.
2. 최악의 경우 시간복잡도가 트리의 높이에 따라 결정된다. 이진 탐색 트리에 비해 효율적이다

Restructuring & Recoloring

R-B Tree는 위의 두 과정에 따라 균형을 유지한다.

 

🔴 Recoloring : 삽입될 노드의 부모 노드가 빨간색이며, 동시에 삼촌 노드가 빨간색인 경우 발생.

Recoloring 의 과정

1. 부모 노드와 삼촌 노드를 검은색으로 변경하고, 조상 노드를 빨간색으로 변경한다
2. 조상 노드를 기준으로 같은 연산을 재귀적으로 진행한다
   • 조상이 루트 노드라면 검은색으로 바꾼다
   • 조상을 빨간색으로 바꿨을때 또 다시 Double Red가 발생한다면 Restructuring / Recoloring 진행해서 Double Red가 발생하지 않을때까지 반복한다.
3. 이 과정을 반복하여 루트까지 Red-Red 문제가 올라가면 루트 노드의 색을 검은색으로 바꾸어 트리의 균형을 유지한다.

▶︎ 1번의 결과로 root가 빨간색이 되었을때 → 2-1 번을 수행한다

 

 

⚫️ Restructuring : 삽입될 노드의 부모 노드가 빨간색이지만 삼촌 노드는 검은색일 경우 발생.

Rotation 과 Recoloring을 동시에 수행한다.

Restructuring의 과정

1. 삼촌 노드가 조부모 노드의 오른쪽 자식이고, 새로운 노드가 부모 노드의 왼쪽 자식인 경우
   • 부모 노드와 조부모 노드에 대해 right rotation 진행
   • 부모와 조부모의 색을 바꾼다
2. 삼촌 노드가 조부모 노드의 오른쪽 자식이고, 새로운 노드가 부모 노드의 오른쪽 자식인 경우
   • 부모 노드와 새로운 노드에 대해 left rotation 진행
   • 1번 과정을 동일하게 수행

• Restructuring 과정 간소화
  1. 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬한다
  2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다
  3. 새로 부모가된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다

검색

RB 트리는 기존 이진 트리의 검색 방법과 동일한 방법을 사용한다. 이진탐색트리의 기본 조건인 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 성질을 만족하기 때문이다.

삽입

삽입은 노드를 삽입하고, 색을 붉은색으로 정하는 것으로 시작한다. 그 다음 단계는 주위 노드 색에 따라 달라진다.

왜 삽입하는 노드는 Red 인가?

→ 삽입 후에도 5번 속성을 만족하기 위해

특성의 변화

• 모든 리프 노드는 검은색인 것은 불변이다.
• 빨간색 노드의 모든 자식은 검은색이라는 특성은 삽입 시 지켜지지 않는 상황이 발생한다
• 어떤 노드로부터 리프 노드까지 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있지 않는 상황이 생긴다. 검은색 노드로의 전환, 회전 때문에 발생한다.

Case 1 : 새 노드가 루트다

삽입한 노드가 루트면 그냥 검정으로 칠한다.

시작점으로부터 뻗어나가는 모든 경로에 검은색 노드를 하나 추가한 셈으로, 5번째 속성(한 노드에서 뻗어나가는 모든 경로에 대해 검은 노드의 수는 같다)은 유효하다.

Case2 : 부모가 검정색

새로운 노드의 부모가 검은색이라면, 새로운 노드는 빨간색이니 문제 없다.

새로운 노드는 두 개의 검은색 노드를 리프 노드로 가진다.

Case3 : 부모가 빨간색

새로운 노드와 부모 모두 빨간색인 경우, 3개의 하위 케이스로 나뉜다.

Case 3-1 : 삼촌도 빨간색

부모랑 삼촌을 검정으로 바꾸고, 조상을 빨강으로 바꿈.

조상을 기준으로 다시 위로 올라가면서 재조정.

 

1. 조상이 루트인 경우, 특성2에 따라 루트를 다시 검은색으로 바꾼다

2. 조상이 루트가 아닌 경우 (상황에 따라 추가 조정 필요할 수 있음)

Case 3-2 : 삼촌은 검정, 삽입 방향이 지그재그 (안쪽)

case3-3과 다른점 : 삽입된 노드를 기준으로 조상까지의 경로가 꺾여있다.

부모가 빨강이고, 삼촌이 블랙일때, 부모를 기준으로 왼쪽 회전한 뒤, 3의 방식으로 해결한다.

Case 3-3 : 삼촌은 검정, 삽입 방향이 일자 (바깥족)

부모는 검정색, 조상은 빨간색으로 바꾼 후 조상을 기준으로 오른쪽으로 회전한다.

 

삭제

속성 위반 여부 확인은 삭제되는 색을 통해 확인한다.

• 삭제되는 색이 빨간색 이라면 어떠한 속성도 위반하지 않는다.
• 삭제되는 색이 검정색 이라면 2, 4, 5 속성을 위반할 수 있다.

1. 삭제되는 색을 먼저 알아야 한다 → 삭제할 노드의 색이 삭제되는 색이 아닐 수 있다. 즉 삭제로 인해 색이 변할 수 있다.
2. 삭제할 노드의 자식이..
   • 2개인 경우: 삭제할 노드의 오른쪽 서브트리의 가장 왼쪽 노드 or 왼쪽 서브트리의 가장 오른쪽 노드로 바꾸고, 리프 노드를 삭제한다 (삭제하려는 노드의 successor의 색을 삭제한다)
   • 1개인 경우 : 삭제되는 색은 삭제할 노드의 색과 일치한다. 삭제되는 노드의 부모와 자식 노드를 연결시킨다
   • 없는 경우 : 바로 삭제
   • 삭제 색 결정 참조
3. 5번 속성을 위반할 경우, 삭제된 색의 위치를 대체할 노드에 extra black을 부여한다

→ 경로에서 black 수를 카운트할 때 extra black은 하나의 black으로 카운트 된다

• black 에 extra black 을 부여한 경우 : doubly black
• red 노드에 extra black을 부여한 경우 : red-and-black

Extra black 부여 후 red-and-black 해결하기

red를 black으로 바꾼다

Extra black 부여 후 doubly black 해결하기

아래의 케이스에 해당하는 내용을 찾아서 해결한다

Case 4

(*왼쪽 오른쪽 바뀌어도 무방. 순서는 동일)

Doubly black 의 오른쪽 형제가 black 이고 그 형제의 오른쪽 자녀가 red일때

1. red를 doubly black 위로 옮기고
2. 옮긴 red로 extra black을 전달해서 red-and-black으로 만든다
3. red-and-black을 black으로 만든다

즉 간소화된 해결 방법

1. 오른쪽 형제는 부모의 색으로
2. 오른쪽 형제의 오른쪽 자녀는 black으로
3. 부모는 black으로 바꾼 후에
4. 부모를 기준으로 왼쪽으로 회전한다

 

Case 3

Doubly black의 오른쪽 형제가 black이고 그 형제의 왼쪽 자녀가 red, 오른쪽 자녀가 black일 때

→ doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 case4를 이용하여 해결

 

Case 2

Doubly black의 형제가 black, 그 형제의 두 자녀 모두 black일때

→ doubly black과 그 형제의 black을 모아서 부모에게 전달하고, 부모가 extra black을 해결하도록 위임

두번째 a의 extra black은 무시

Case 1

Doubly black의 오른쪽 형제가 red일때

→ 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 doubly black을 기준으로 case 2, 3, 4 중 하나로 해결

 

 

---

참조 문헌

https://www.youtube.com/watch?v=SHdYv41iCmE&t=35

 

https://arc.net/l/quote/svgxxqjj

[알고리즘] 레드-블랙 트리의 시간복잡도가 O(log n)인 이유

 

https://www.youtube.com/watch?v=2MdsebfJOyM

 

https://www.youtube.com/watch?v=6drLl777k-E&t=24s