[TIL] 크래프톤 정글 5주차 - 자료구조(RB Tree)

Red-Black Tree란?

출처 : https://velog.io/@main_door/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99%ED%8A%B8%EB%A6%AC

 

- 이진 탐색 트리(BST)의 한 종류

 

- 스스로 균형을 잡는(self-balanced) 트리

 

- BST의 worst case의 단점을 개선

 

- 모든 노드는 red 혹은 black

Red-Black Tree의 속성

1. 모든 노드는 red 혹은 black

 

2. 루트 노드는 black

 

3. 모든 nil(leaf) 노드는 black

 

nil 노드란?

- 존재하지 않음을 의미하는 노드

 

- 자녀가 없을 때 자녀를 nil 노드로 표기(null이면 nil노드로 표기)

 

- 값이 있는 노드와 동등하게 취급

 

- RB 트리에서 leaf 노드는 nil 노드

 

 

4. red의 자녀들은 black이다.(red가 연속적으로 존재할 수 없다.)

 

5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

black height란?

노드 x의 black height : 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트에서 제외)

 

5번 속성을 만족해야 성립하는 개념

색을 바꾸면서도 5번 속성 유지

RB 트리가 5번 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

RB 트리는 어떻게 균형을 잡는가?

- RB 트리에서 삽입 / 삭제 시 주로 4번, 5번 속성을 위반한다.(2번을 위반하기도 함)

 

- 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

RB Tree에서의 삽입

Red Black Tree에서 노드를 삽입할 때, 삽입하는 노드의 색깔은 반드시 Red이다.

 

먼저 RB Tree에서의 삽입에서 3가지 Case가 있다.

Case 1) 삼촌 노드가 red인 경우

출처 : https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/

· 부모 노드와 삼촌 노드를 black으로 바꾼다.

 

· 할아버지 노드를 red로 바꾼다.

 

· 할아버지 노드에서 불균형이 발생할 수 있으므로, 할아버지 노드를 추가된 노드로 설정하고 불균형 복구 함수를 재귀 호출한다.

Case 3) 삼촌 노드가 black이고 부모 노드, 새 노드가 left / right 자식인 경우

출처 : https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/

· 부모 노드를 기준으로 right / left 회전을 수행한다.

 

· 부모 노드와 형제 노드(회전 이전의 삼촌 노드)의 색상을 바꾼다.

Case 2) 삼촌 노드가 black이고 부모 노드가 left / right 자식이고, 새 노드가 right / left 자식인 경우

· 새 노드를 기준으로 left / right 회전 후, right / left 회전을 수행한다.

 

· 새 노드와 자식 노드의 색상을 바꾼다.(자식 노드는 회전 수행 후 생긴 자식이다.)

RB Tree에서의 회전

· RB tree에서의 rotation은 노드 기준으로 right / left 로 나뉜다.

 

다음과 같은 그림에서 x를 기준으로 left rotation을 적용하면 다음과 같다.

 

 

이번에는 y를 기준으로 right rotation을 적용하면 다음과 같다.

 

RB 트리에서는 각각의 세가지 case에서 rotation과 recoloring을 통해 5가지 조건을 만족시킨다.

(rotation 사진 출처 : https://www.codesdope.com/course/data-structures-red-black-trees-insertion/)

RB 트리에서의 삭제

RB트리에서의 삭제는 기본적으로 BST의 삭제 방식을 따른다. 어떤 노드를 삭제할 때 그 노드의 successor, 즉 자기보다 큰 노드 중 가장 작은 값을 가진 노드를 삭제할 노드의 자리로 끌고 올라온다.

BST에서의 삭제(successor version) (출처 : https://stackoverflow.com/questions/60059783/why-is-the-successor-of-a-bst-node-defined-as-the-one-larger-than-the-deleted-on)

 

삭제 후 속성 위반 여부를 확인하는 방법부터 말하겠다.

 

- 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색 = 삭제되는 노드의 색 이다.(자녀 = 유효한 값을 가지는 노드(nil X))

 

- 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor의 색

 

레드 블랙 트리에서 삭제 후 속성 위반 여부 확인은 삭제되는 색을 통해 알 수 있다.

 

- 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다. 따라서 아무 일도 일어나지 않으므로 그대로 상황 종료가 된다.

 

- 삭제되는 색이 black이라면 2, 4, 5번 속성을 위반할 수 있다.

삭제 후 2번 속성 위반하는 경우

- 삭제 후 2번 속성을 위반하는 경우는 단순하게 root 노드의 색을 black으로 바꾸기만 하면 된다.

삭제 후 5번 속성을 위반하는 경우(특수한 상황을 제외하면 항상 5번 위반)

- 삭제가 된 후, 5번 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다.

 

Extra black의 역할

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

Doubly black

 

extra black이 부여된 black 노드

red - and - black

extra black이 부여된 red 노드

 

 

Red-and-black을 해결하는 방법

red-and-black을 black으로 바꾸면 해결된다.

Doubly black을 해결하는 방법

doubly black의 형제의 색과 그 형제의 자녀들의 색에 따라 총 4가지 case로 분류가 된다.

Case 4) Doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때

 

한 줄로 요약하자면 E에 있는 red를 doubly black 위로 옮겨서 extra black을 해당 red로 옮겨 red-and-black으로 만들면,

red-and-black을 black으로 바꾸기만 하면 해결된다.

 

1) red를 왼쪽으로 옮기려면 d의 위치가 red가 되어야하는데 여기서 RB tree의 특성을 이용한다.

(D의 입장에서 5번 속성을 만족하고 있으므로 D와 두 자녀의 색을 바꾸어도 5번 속성을 여전히 만족한다는 특성)

 

2) red가 왼쪽으로 갈 수 있도록 회전 전에 B와 D의 색을 바꾼다.

 

3) B기준 왼쪽으로 rotate한다.

 

4) A와 C의 extra black을 모아 B로 전달하여 B를 black으로 만든다.

 

결과론적으로 간단히 말하면 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 해결된다.

Case 3) Doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red일 때 & 그 형제의 오른쪽 자녀가 black일 때

 

 

한 줄 요약을 하면 doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 case 4를 적용하여 해결하면 된다.

 

E 위치에 red가 오도록 만들기 위해 C와 D의 색을 바꾼 후에 D를 기준으로 오른쪽으로 회전하면 된다.

 

그렇게 되면 Case 4가 완성이 되어 위 방법을 적용만 하면 해결된다.

Case 2) Doubly black의 형제가 black & 그 형제의 두 자녀 모두 black일 때

 

A와 A의 형제인 D의 black을 모아서 부모에게 전달하게 되면 A와 D에서 black을 모았기 때문에 A는 여전히 black이고 D는 red가 된다.

 

그렇게 되면 부모 B는 red-and-black이거나 doubly black이 된다.

 

1) 부모가 red-and-black이라면 부모를 black으로 바꿔주면 상황 종료

 

2) 부모가 doubly black일때, 부모가 root 노드라면 black으로 바꿔주면 끝나지만, 루트 노드가 아니라면 부모의 위치에서 case 1, 2, 3, 4 중에 하나로 해결하면 된다.

 

정리하면 doubly black과 그 형제의 black을 모아 부모에게 extra black 형태로 전달해서 부모가 extra black을 해결하도록 위임하는 방법이다.

Case 1) Doubly black의 형제가 red일 때

 

간단히 말하면 doubly black의 형제를 black으로 만든 후 case 2, 3, 4 중에 하나로 해결하면 된다.

 

형제를 black으로 만드는 방법은 B를 기준으로 왼쪽으로 회전시켜 case 2, 3, 4중 하나로 만들어 해결하는 것인데, 이 때 5번 조건을 위반하는 것을 방지하기 위해 부모 B와 지금의 형제 D의 색을 바꾼 뒤 회전 시켜 D를 형제로 만들어 해결하면 된다.

 

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

 

 

위의 Case 1, 2, 3, 4 모두 오른쪽 왼쪽을 바꿔도 성립하므로 방향은 상관없다.

 

 

삭제 그림 전체 출처 : https://velog.io/@park485201/red-black-tree-%ED%8A%B9%EC%84%B1-%ED%9A%8C%EC%A0%84-%EC%82%BD%EC%9E%85-%EC%82%AD%EC%A0%9C

Red Black Tree의 시간 복잡도

 

 

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