1. RBTREE란?

🔎 Red-Black Tree란?

• self-balancing binary search tree의 일종이다.
• 각 노드 당 한 비트의 추가 기억 공간을 가지는데, 이 비트는 노드의 색상 정보를 빨간색 또는 검은색으로 저장한다.
• 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되어 근사적으로 균형을 이룬 트리가 된다.
• 트리를 self-balancing 하게 만들어주어 검색, 삽입, 삭제 연산을 모두 **O(log n)**의 시간 복잡도를 보장하며, 이진 탐색 트리와 달리 최악의 경우에도 균형이 깨지지 않도록 보장한다.
• unpredictable tree: 삽입 연산이 항상 일정한 속도로 실행되는 것을 보장하지 않는다.

🚨 Red-Black Tree의 규칙

1. 모든 노드는 빨강 또는 검정색이다.
2. 루트 노드는 검정색이다.
3. 모든 리프 노드는 검정색이다. (NIL 노드를 리프 노드로 취급한다.)
4. 빨간색 노드의 부모 노드와 자식 노드는 모두 검정색이다.
    ⇒ 빨간색 노드는 연달아 두 번 나오면 안된다
5. 어떤 노드에서 시작하여 해당 노드의 하위 트리에 속한 모든 경로는, 해당 노드에서부터 시작하여 리프 노드까지 이동하는 모든 경로와 같은 수의 검정색 노드를 가진다. 이를 RBT의 "균형" 조건이라고 한다

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

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