유튜브 영상 내용을 정리한 포스팅 입니다!!
노션이 더 가독성이 좋으니 되도록 노션으로 봐주세요!
👩🏻‍💻 노션 링크
📹 참고 유튜브 영상

RB Tree란?

🔍 RB Tree 개념

• 이진 탐색 트리의 한 종류
• 스스로 균형 잡는 트리
• 이진 탐색 트리의 worst case(⇒ 한쪽으로 편향되는…)의 단점을 개선
• 모든 노드는 Red or Black

🔍 RB Tree 속성

1. 모든 노드는 Red or Black
2. 루트 노드는 Black
3. 모든 nill(leaf)노드는 Black
   • nil 노드란?
     • 존재하지 않음을 의미하는 노드
     • 자녀가 없을 때 자녀를 nil 노드로 표기
     • 값이 있는 노드와 동등하게 취급
     • RB 트리에서 leaf 노드(=자녀가 없는 노드) nil 노드
4. red의 자녀들은 black / red가 연속적으로 존재할 수 없다
5. 임의의 노드에서 자손 nill 노드들까지 가는 경로의 black수는 같다
   (자기 자신은 카운트에서 제외)
   

🔍 RB Tree는 어떻게 균형을 잡는가?

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

🔍 RB Tree의 삽입 방식

💡 삽입 OVERVIEW

1. 삽입 전 RB 트리 속성 만족한 상태
2. 삽입 방식은 일반적인 이진탐색트리와 동일
   

<이진탐색트리 삽입 방식>
1. Root에서 시작합니다.
2. 삽입 값을 루트와 비교합니다. 루트보다 작으면 왼쪽으로 재귀하고 크다면 오른쪽으로 재귀합니다.
3. 리프 노드에 도달한 후 노드보다 크다면 오른쪽에 작다면 왼쪽에 삽입합니다.

3. 삽입 후 RB 트리 위한 여부 확인
4. RB 트리 속성을 위반했다면 재조정
5. RB 트리 속성을 다시 만족

💡 삽입 노드의 색?

삽입하는 노드는 항상 red다!!!!!
( ⇒ 삽입한 후에도 5번 속성을 만족하기위해 )

💡 삽입 후 위반 case

삽입 후4번 속성을 위반하였을 때, 구조를 바꾸게 되면 이진탐색트리의 특징이 무너진다. ⇒ 구조를 바꾸면서도 이진탐색트리의 특징을 유지시키는 방법은 회전이다.

✔️ case 3)

부모와 할아버지의 색을 바꾼 후, 할아버지 기준으로 오른쪽(왼쪽)으로 회전한다.

✔️ case 2)

부모를 기준으로 왼쪽(오른쪽)으로 회전한 뒤 3번 케이스 방식으로 해결

✔️ case 1)

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

🔍 RB Tree의 삭제 방식

💡 삭제 OVERVIEW

1. 삭제 전 RB 트리 속성 만족한 상태
2. 삭제 방식은 일반적인 이진탐색트리와 동일
3. 삭제 후 RB 트리 속성 위반 여부 확인 ⇒ 어떻게 확인?
4. RB 트리 속성을 위반했다면 재조정
5. RB 트리 속성을 다시 만족

💡 삭제 후 속성 위반 여부 확인 방법

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

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

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

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

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

💡 삭제 후 속성 위반 해결하기

1. 2번 속성 위반 해결하기

   → 루트 노드를 black으로 바꾸면 된다

2. 5번 속성 위반 해결하기

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

   → extra black을 부여받은 노드는 doubly black이 되거나 red-and-black이 된다

   (삭제 되는 색이 black일 때 특수한 상황을 제외하면 5번 속성을 항상 위반하게 된다.)

   • ⭐️extra black의 역할⭐️

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

     

     → doubly black 발생 (extra black이 부여된 black 노드)

     

     → red and black 발생 (extra black이 부여된 red 노드)
     

   2-1. red-and-black 해결하기

   red-and-black을 black으로 바꾸면 해결!!!

   2-2. doubly black 해결하기

💡 doubly black 해결하기

case를 분류할 때의 기준은 doubly black의 형제의 색과 그 형제들의 자녀들의 색

✔️ case 4)

doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때

→ 그 red를 doubly black 위로 옮기고 옮긴 red로 extra black을 전달해서 red-and-black으로 만들면!!!!! red-and-black을 black으로 바꿔서 해결

⇒ 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 해결

✔️ case 3)

doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black일 때

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

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

✔️ case 2)

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

→ B가 red-and-black이 됐다면 black으로 바꿔주면 상황은 종료되지만 B가 doubly black이 됐다면 B가 루트 노드라면 black으로 바꿔서 해결, 아니라면 case 1,2,3,4 중에 하나로 해결

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

✔️ case 1)

doubly black의 형제가 red일 때

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

D를 black으로 만들기 위해서 B와 D 색상을 바꿔준다. 그리고 B를 기준으로 왼쪽으로 회전한다.

이 상태에서 다른 case를 적용

🔍 시간 복잡도

N = 트리의 노드 수

	avg	worst
insert	O(logN)	O(logN)
delete	O(logN)	O(logN)
search	O(logN)	O(logN)

💡 AVL 트리와 비교

• 삽입/삭제가 거의 없고 검색이 대부분인 상황에서는 AVL트리를 사용하고, 삽입/삭제가 많을 때는 RBTree를 사용하면 좋다.
• 왜냐하면 AVL트리는 검색 성능이 빠르고 RBTree는 삽입/삭제 성능이 좋다.
• AVL트리는 균형을 좀 더 엄격하게 잡는다. 엄격하니까 검색 성능은 더 좋지만 삽입/삭제는 RBTree에 비해 느리다.

참고자료
[정글] 레드블랙트리 동작 (Red Black Tree) - Insert 편
[WEEK 05] C - 레드-블랙 트리
C언어로 구현하는 | 레드블랙트리
Red-Black Tree