Red-Black 트리

• 이진 탐색 트리(BST)의 한 종류
• 스스로 균형을 잡는 트리
• BST의 worst case의 단점을 개선(한 쪽으로만 치우쳐지는 경우)
• 모든 노드는 red 혹은 black
  

Red-Black 트리의 속성

• 1. 모든 노드는 red 혹은 black
• 2. 루트 노드는 black
     
• 3. 모든 nil(leaf) 노드는 black

nil 노드란?

• 존재하지 않음을 의미하는 노드
• 자녀가 없을 때 자녀를 nil 노드로 표기
• 값이 있는 노드와 동등하게 취급
• RB트리에서 leaf 노드는 nil 노드
  

• 4. red의 자녀들은 black or red가 연속적으로 존재할 수 없다.
• 5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

     노드 x의 black height

  • 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서 black 수(자기 자신은 카운트에서 제외)
  • 5번 속성을 만족해야 성립

색을 바꾸면서도 5번 속성 유지하기 RB트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족(임의의 노드에서 자손 nil 노드들까지는 가는 경로들의 black 수는 같다)

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

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

• 4. red의 자녀들은 black or red가 연속적으로 존재할 수 없다.
• 5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

삽입

• 0. 삽입 전 RB트리 속성 만족한 상태
• 1. 삽입 방식은 일반적인 BST와 동일
• 2. 삽입 후 RB 트리 위반 여부 확인
• 3. RB트리 속성을 위반했다면 재조정
• 4. RB 트리 속성을 다시 만족

삽입 노드의 색

• 삽입하는 노드는 항상 red다

삽입 예제

insert(50)
노드를 삽입할 때 두 nil 노드의 색은 black으로 고정한다. 그러면 자연스럽게 3번 속성 만족

하지만 지금 상태는 RB트의 2번 속성을 위반 루트 노드를 black 으로 바꾸면 해결

insert(20)

RB트리의 모든 속성을 만족

왜 새로 삽입하는 노드는 red인가?
삽입 후에도 5번 속성을 만족하기 위해

CASE.3

insert(10)

RB트리의 4번 속성 위반
red가 한쪽으로 몰려 있으니 red 하나를 반대편으로 옮겨준다면?!

이런식으로 구조를 바꿔준 뒤에 BST의 특징 또한 유지 되어야 함.
구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전이다.

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

2. 50을 기준으로 오른쪽으로 회전
4번 속성을 포함한 RB트리의 속성들을 모두 만족

CASE.3 해결하기(오른쪽 왼쪽을 바꿔도 성립)

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

---

CASE.2

insert(40)

RB트리 속성 위반

4번 속성 위반을 해결하기 위해 red 하나를 넘겨야하는데 BST 특징 또한 유지하면서 넘기려면 회전을 사용해야한다. 회전을 어떻게 사용할지가 관건이다.
case.3와 다른 점은 삽입된 노드를 기준으로 할아버지까지의 경로가 꺾였다.
꺽인 부분을 펴줘서 case.3와 같은 형태로 만들면 case.3과 같은 방식으로 해결 가능

1. 20 기준으로 왼쪽으로 회전한다.
   회전 후에도 4번 외의 속성들을 만족하며 이제 case.3 형태가 됨
   
2. 40과 50의 색을 바꾼다
   
3. 50 기준으로 오른쪽 회전한다.
   

CASE.2 해결하기(오른쪽 왼쪽을 바꿔도 성립)

삽입된 red의 노드가 부모의 오른쪽 자녀
& 부모도 red고 할아버지의 왼쪽 자녀
& 삼촌(=부모의 형제)은 black이라면 부모를 기준으로 왼쪽으로 회전한 뒤 case.3의 방식으로 해결

---

CASE.1

insert(30)

RB트리 4번 속성 위반 red가 한 쪽으로 몰려 있지 않아서 옮길 수가 없다.

4번을 만족시키면서 5번을 유지하려면 10과 50을 블랙으로 바꾸고 20을 레드로 바꾸면 된다.

하지만 20이 루트 노드라 2번 속성을 위반 -> 20을 black으로 바꾸기

CASE.1 해결하기

삽입된 red 노드의 부모도 red
& 삼촌(=부모의 형제)도 red라면
부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에게 다시 확인을 시작

RB트리 예제

insert(80)

insert(40)

4번 속성을 위반한 case.1 상태 -> 부모와 삼촌을 black으로, 할아버지는 red로 변경

할아버지인 50에서 확인 후 모든 속성을 만족하기 떄문에 상황 종료

insert(35)

4번 속성을 위반한 case.2 상태 40을 기준으로 오른쪽으로 회전해서 case.3의 형태로 만들기

4번 속성을 위반한 case.3 상태 30과 35의 색을 바꾸고

30을 기준으로 왼쪽으로 회전

RB트에 속성을 만족

insert(25)

4번 속성을 위반한 case.1 상태! 부모와 삼촌을 black으로, 할아버지는 red로 변경

할아버지는 35에서 확인 시 4번을 위반한 case.2상태! 50을 기준으로 오른쪽으로 회전해서 case.3의 형태로 만들기

4번 속성을 위반한 case.3 상태이므로 20과 35의 색을 바꾸고

20을 기준으로 왼쪽으로 회전

출처

쉬운코드 유튜브
https://www.youtube.com/watch?v=6drLl777k-E&ab_channel=%EC%89%AC%EC%9A%B4%EC%BD%94%EB%93%9C