레드 블랙 트리 (Red-Black Tree, RB-Tree)

앞서 이진 탐색 트리에 대해 살펴봤듯이, 이진 탐색 트리는 한쪽으로 쏠릴 경우 시간 복잡도가 O(n) 으로 상승하는 것을 알 수 있었다. 이러한 문제를 보완하고자 나온 트리 중 하나가 레드 블랙 트리다.

🎅 레드 블랙 트리란?

레드 블랙 트리란, BST의 일종으로 각 노드가 Red 또는 Black의 색상을 가짐으로써 스스로 균형을 유지하는 트리다.

그 결과로 검색, 삽입, 삭제 시 모두 O(logN) 이 보장된다.

NIL node

레드 블랙 트리에는 NIL node라는 개념이 있다.

NIL node는 자식 노드가 존재하지 않는 경우, NIL node라는 특수한 노드가 있다고 생각하면 된다!

따라서 모든 leaf node는 NIL node가 된다.

또한 root의 부모도 NIL node라 가정하자.

Left and Right Rotate

레드 블랙 트리 뿐만 아니라, 균형을 유지하는 트리에서 트리의 균형을 맞추기 위해 Rotate를 할 때가 있다.

• Left Rotate
• Right Rotate
  • 위와 반대로 하면 된다!

레드 블랙 트리의 조건

레드 블랙 트리는 아래 5가지 조건을 모두 충족해야 한다.

1. 각 노드의 색은 Red 또는 Black이다.
2. 루트 노드는 Black이다.
3. 모든 leaf node는 Black이다. (NIL = Black)
4. Red 노드의 자식 노드들은 전부 Black이다. (즉, Red 노드는 연속되어 등장할 수 없다.
5. 루트 노드에서 시작해서 자손인 leaf node에 이르는 모든 경로에는 동일한 개수의 Black 노드가 존재한다.

🤖 동작 과정

레드 블랙 트리에서는 삽입, 삭제 할 때 위의 조건을 충족시키면서 동작한다.

조건을 만족하기 위해 노드의 색을 변경하기도 하고, Rotate를 하기도 한다.

만약 레드-레드가 만났다면, 다음과 같이 처리하면 된다!

• 삼촌이 레드일 때
  • 부모와 삼촌의 색깔을 black으로 바꾸고 할아버지의 색깔을 바꾼다.
• 삽입될 노드가 부모의 오른쪽 자식인 경우
  • 부모를 기준으로 좌회전한다.
• 삽입될 노드가 부모의 왼쪽 자식인 경우
  • 할아버지를 기준으로 우회전한다.