🔍 RB Tree 개념

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

🔍 RB Tree 속성

1. 모든 노드는 Red or Black

2. 루트 노드는 Black

3. 모든 nill(leaf)노드는 Black

   • nil 노드란?

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

5. 임의의 노드에서 자손 nill 노드들까지 가는 경로의 black수는 같다

   (자기 자신은 카운트에서 제외)

   • 노드 x의 black height

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

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

🔍 RB Tree의 삽입 방식

💡 삽입 OVERVIEW

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