정의 및 특징

<aside> 💡

Red-Black Tree 혹은 RB Tree란,

자가 균형 이진 트리(Self-Balancing Search Tree)의 일종으로, 각 노드가 Red or Black의 속성을 가지는 트리

</aside>

• 이진 트리의 특수한 형태
  • RB 트리의 경우, 리프 노드가 비어있고, 자료를 갖지 않음
• 최악의 경우에도 일정한 실행 시간을 보장 : Worst-Case Guarantees
  • 트리에 n개의 원소가 있을 때, O(log n)으로 삽입 / 삭제 / 검색이 가능
  • 때문에 실시간 처리와 같은 실행시간이 중요한 경우 유용하게 쓰임

<aside> 💡

RB Tree의 5가지 속성

</aside>

• 모든 노드는 빨간색 또는 검은색

• 루트 노드는 항상 검은색

• 모든 리프(NIL)은 검은색

• 빨간 노드의 자식은 모두 검은색 → No Double Red

• 어떤 노드에서 리프(NIL)까지 가는 모든 경로에는 같은 수의 검은색 노드(Black-Height)가 있음

  Black-Height

  • 한 노드 x에서 리프까지의 경로에 있는, x 자신은 제외한 모든 블랙 노드의 개수를 의미

<aside>

Example of Red-Black Tree, Introduction to Red-Black Tree, GeeksforGeeks

</aside>

• Correct Red-Black Tree
  • Black-Height가 일치함 : 루트 노드를 제외하고는 검은색 노드가 각 하나씩 있음
• Incorrect Red-Black Tree
  • 두 개의 빨간 노드가 서로 인접함 : RB Tree의 속성을 따르지 않음
  • 한 경로에는 검은색 노드가 전혀 없음 : Black Height가 맞지 않음