Red Black Tree(레드-블랙 트리)

 

Red Black Tree란?

이진 탐색 트리의 한 종류로 스스로 균형을 잡는 밸런스 트리입니다.

BST(이진탐색트리)의 worst case의 단점을 개선 - 이진 탐색 트리는 최악일 경우 O(N)의 시간복잡도를 가짐

 

 

RB Tree의 속성

1. 모든 노드는 red 혹은 black이다.
2. 루트 노드는 black이다.
3. 모든 nil 노드는 black 컬러를 가진다. ( RB 트리에서 리프 노드는 nil 노드)
4. red의 자녀들은 반드시 black. 즉, red가 연속적으로 존재할 수 없다. black은 가능!
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외함)

 

노드 x의 black height = 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수

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

 

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

RB 트리가 5번 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때

부모와 두 자녀의 색을 바꿔도 5번 속성은 여전히 만족한다.

 

삽입

과정

삽입 전에는 속성을 모두 만족한 상태

삽입 방식은 이진탐색트리와 동일

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

속성을 위반했다면 재조정

속성을 다시 만족

 

! 삽입하는 노드는 항상 red

nil 노드는 black 고정

 

2번 속성 위반시 루트를 블랙으로 바꿔주면 됨

 

>> 왜 새로 삽입하는 노드는 red인가?

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

임의의 조상 노드에서 nil까지 블랙 수를 셀 때,

블랙을 삽입하면 특정 루트만 블랙이 늘어남 - 레드를 삽입할 경우 5번 속성을 만족할 수 있음

 

속성 위반 시 구조를 바꿔야하는데 구조를 바꾸면서 BST를 유지하려면 회전을 해야한다.

 

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

case 3.

삽입된 red 노드가 부모의 왼쪽 자녀&

부모가 red면서 할아버지의 왼쪽 자녀와 부모의 형제가 black이라면 부모와 할아버지의 색을 바꾸고 할아버지 기준으로 오른쪽으로 회전한다.

 

case 2.

case3 와 다른 점은 삽입한 노드부터 할아버지 노드까지 경로가 꺾였다

(삽입 노드가 부모의 오른쪽 자녀면서 부모가 red && 할아버지의 왼쪽 자녀&&삼촌이 black이라면)

꺾인 부분을 펴주고 case3처럼 만들어줌

-> 부모를 기준으로 왼쪽으로 회전한 뒤 case3 방식으로 해결

 

case 1.

삽입 노드의 부모도 red & 삼촌도 red라면

-> 부모와 삼촌을 balck으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에서부터 다시 확인을 시작한다

 

 

삭제

삭제 전에는 RB트리 속성을 만족한 상태임을 가정

삭제 방식은 BST와 동일

삭제 후 RB 트리 속성 위반 여부 확인

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

RB 트리 속성을 다시 만족

 

 

nil 제외한 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색 = 삭제되는 노드의 색이다.

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

 

속성 위반 여부 확인는 삭제되는 색을 통해서 할 수 있다.

 

삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다!

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

 

 - 2번 위반 시

= 새로 루트가 된 노드를 black으로 바꿔주면 끝

 

- 5번 위반 시

= 삭제된 색의 위치를 대체한 노드에 extra black 부여

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

extra black을 부여받는 노드가 블랙일 때 -> doubly black // 레드일 때 -> red-and-black

 

extra black 해결하기

red-and-black -> 그냥 black으로 바꾸면 해결

 

doubly black 해결하기

case 4.

doubly black의 오른쪽 형제가 black이면서 -> D

그 형제의 오른쪽 자녀가 red일 때 -> E

 

doubly black 위 노드를 red로 만들고 extra black을 전달

 

1. D의 블랙을 자식들로 전파 / E는 블랙이 되고 다른 자녀 C는 레드->블랙 또는 doubly black이 된다.

2. D의 부모인 B와 색을 바꾼다.

3. 부모 B를 기준으로 왼쪽으로 회전한다.

4. doubly black을 red가 된 B로 전해준다.

 

요약)

오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로 부모는 블랙으로 바꿈

부모를 기준으로 왼쪽으로 회전하면 해결

 

case 3.

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

-> doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 이후엔 case 4를 적용해 해결

 

먼저 왼쪽 자녀와 형제의 색을 바꾸고 형제를 기준으로 오른쪽으로 회전, 

이후는 case 4

형제는 부모의 색으로 바꾸고 부모와 오른쪽 자녀를 black 바꾼 후 B 를 기준으로 왼쪽으로 회전해서 해결

 

 

case 2.

doubly black의 형제가 black이고 그 형제의 두 자녀 모두 black일 때

doubly black과 그 형제의 black을 모아 부모에게 전달! 부모가 extra black을 해결하도록 위임한다.

 

부모는 red-and-black 또는 doubly black이 된다.

red-and-black이면 블랙으로 바꿔주면 해결

doubly black이면 case 1,2,3,4 중에 해결 - 만약 루트면 그냥 black으로 해결

 

 

case 1.

형제가 red 일 때 형제를 black으로 만든 후 case 2,3,4 중에서 해결

 

먼저 부모(black)를 기준으로 왼쪽으로 회전/ 그 전에 먼저 부모와 형제의 색을 교환

회전으로 doubly black의 형제가 black이 되었으므로 case 2,3,4 중에 해결책을 찾음