Red-Black 트리

Red-Black 트리란

- 이진 탐색 트리(BST)의 한 종류로 스스로 균형을 잡는 트리로써 BST의 worst case(한쪽으로 편향이 되어있는 상태에서 삽입 삭제 검색의 시간 복잡도는 O(N)으로 오래걸린다.)의 단점을 개선했다. 모든 노드는 red혹은 black으로 표현

Red-Black트리의 5가지 속성

1. 모든 노드는 red 혹은 black

 

2. 루트 노드는 black

 

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

* 중요nil 노드란? - 존재하지 않음을 의미하는 노드, 자녀가 없을 때 자녀를 nil 노드로 표기, 값이 있는 노드와 동등하게 취급, RB트리에서 leaf 노드는 nil 노드(파란색 동그라미)

 

 

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

 

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

* 노드x의 black height - 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수

* 색을 바꾸면서도 5번 속성 유지하기 - 두자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

 

RB트리에서의 높이

노드 x의 높이h(x)는 자신으로부터 리프노드까지의 가장 긴경로에 포함된 edge의 개수이다.

노드 x의 높이 bh(x)는 x로부터 리프노드까지의 경로상의 블랙노드의 개수이다.(노드x 자신 불포함)

높이가 h인 노드의 블랙높이는 조건4에 의해 레드 노드가 연속될 수 없으므로 bh >= h/2 이다.

 

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

삽입/삭제 시 주로 4,5번 속성을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다

* 4번 속성 - 노드가 red라면 자녀들은 black 5번 속성 - 임의의 노드에서 자손 nil노드까지 가는 경로의 black수는 같다

 

삽입 overview

0. 삽입 전 RB트리 속성 만족한 상태

1. 삽입 방식은 일반적인 BST와 동일

2. 삽입 후 RB 트리 위반 여부 확인

3. RB트리 속성을 위반했다면 재조정

4. RB트리 속성을 다시 만족

* 삽입 노드의 색은 항상 red이다. 왜? - 삽입 후에도 5번 속성을 만족하기 위해서

 

삽입 시 예제(case)

1. red삽입 후 2번 속성을 위반했을때 해결

- 루트노드를 black으로 바꿔준다.

2. red 삽입 후 4번 속성을 위반했을때

 

case 1. 자식노드가 red이며 오른쪽으로 꺾여있고 부모도 red 삼촌(부모의 형제)도 red일때

부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼뒤 할아버지에서 다시 RB트리 속성 확인을 시작한다

 

case 2. 자식노드가 오른쪽 red로 꺾여있을때

- 삽입된 red 노드가 부모의 오른쪽* 자녀일때 부모도 red이고 할아버지의 왼쪽* 자녀와 삼촌이(=부모의 형제) black 이라면 부모를 기준으로 왼쪽으로 회전한 뒤 case3 방식으로 해결한다. -> 꺾인 노드 삽입시에 (오른쪽 왼쪽을 바꿔도 성립)

 

case 3. 자식 노드가 왼쪽 red일때(한쪽으로 몰려있을때)

- 몰려있는 red를 반대편으로 회전시켜 옮겨주는 방법

- 삽입된 red 노드가 부모의 왼쪽자녀이고 & 부모도 red면서 할아버지의 왼쪽 자녀이고 & 삼촌(=부모의 형제)은 black이라면 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽으로 회전한다(오른쪽 왼쪽을 바꿔도 성립한다.)

* 구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전이다

회전 방법

1. 20과 50의 색을 바꿔준다.

2. 50을 기준으로 오른쪽으로 회전한다.

 

Restructuring 과정 (블랙 삼촌)

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

Recoloring 과정 (레드 삼촌)

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
   1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
   1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

암튼 삽입하는 노드를 기준으로 삼촌 즉 부모의 형제가 검정이라면 Restructuring(회전)

레드라면 Recoloring(색깔 바꿔) 해준다.

 

삭제 overview

0. 삭제 전 RB트리 속성 만족한 상태

1. 삭제 방식은 일반적인 BST와 동일

2. 삽입 후 RB 트리 위반 여부 확인

3. RB트리 속성을 위반했다면 재조정

4. RB트리 속성을 다시 만족

* 삭제되는 색을 통해 속성 위반 여부 확인 (매우 중요)

-> 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색은 = 삭제되는 노드의 색

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

successor란 - 그 노드의 자식 오른쪽에서 가장 작은 노드의 값

-->>> 삭제되는 색이 red라면 RB트리의 어떠한 속성도 위반하지 않는다.

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

2- 루트노드는 black, 4 - 노드가 red라면 자녀들은 black, 5- 임의의 노드의 blackheight 수는 같다

삭제 시 예제(case)

1. m이 레드인 경우는 그냥 삭제하면된다.

2. m이 블랙이고 자식이 레드인 경우는 삭제후 x의 노드를 블랙으로 바꾸면된다.

3. m과 x가 블랙인 경우는 m을 삭제한다면 블랙노드의 개수가 부족해서 RB트리 4번에 위반된다.

따라서 x의 주변 상황에 따라 처리 방법이 달라진다.

case 1 - 1 : p가 red

p와 s의 색상을 맞바꾼다

case * - 2: 

p를 중심으로 왼쪽으로  Restructuring r을 레드에서 블랙으로 바꾼다

case * - 3:

s를 중심으로 오른쪽으로 Restructuring l과 s의 색을 바꾼다. case * - 2로 이동

case 2 - 1: 

RB트리의 5번 속성을 위반함으로 s를 레드로 바꿔준다.

case 2 - 4:

p를 중심으로 왼쪽으로 회전시키고 s와 p의 색을 바꾼다 그다음 case1, 1-2, 1-3 중 하나로 이동한다.

 

레드-블랙 트리 시뮬레이터

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

 출처: https://www.youtube.com/watch?v=6drLl777k-E

출처: https://itstory.tk/entry/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACRed-black-tree

출처: https://code-lab1.tistory.com/62