[자료구조]Red-Black 트리(레드블랙트리)

Red-Black Tree

• 탐색, 삽입, 삭제 성능: O(log₂n)
• 탐색, 삽입, 삭제에 binary search tree 알고리즘 사용
• 각 노드는 색상이 할당됨

Properties(Rules)

• 각 노드는 red 노드거나 black 노드다
• 루트 노드는 black 노드다
• 모든 leaf 노드는 black 노드다(NIL 포함)
• 모든 red 노드는 반드시 2개의 black 노드를 자식으로 갖는다
• 주어진 어떤 노드에서든 자식 노드까지 모든 경로에서 같은 수의 black 노드를 갖는다

Insertion

• 새로운 노드는 red 노드 상태로 binary search tree 삽입
• uncle 노드를 확인해서 밸런스를 맞춘다
• 삽입에는 5가지 경우가 있을 수 있다
  (N: 삽입하는 노드(red) P: N의 부모 노드, G: N의 조부모 노드, U: N의 삼촌 노드(P의 형제 노드))
  1. N이 root node
     • N의 색상을 black으로 바꾼다
  2. P가 black 노드
     • 그대로 진행한다
  3. P와 U가 red 노드
     • P와 U가 red 노드면 G는 black 노드
     • N이 red 노드이므로 P와 U를 black 노드로 바꾸고, G를 red 노드로 바꾼다
     • 규칙에 위배되는 경우, 해당 규칙을 따르기 위한 방법을 수행한다
  4. N이 G의 왼쪽 자식의 오른쪽 자식으로 추가되거나, N이 G의 오른쪽 자식의 왼쪽 자식으로 추가되는 경우(P는 red, U는 black)
     • N이 G의 왼쪽 자식의 오른쪽 자식으로 추가되는 경우 Rotation 수행
     • 규칙에 위배되는 경우, 해당 규칙을 따르기 위한 방법을 수행한다
  5. N이 G의 왼쪽 자식의 왼쪽 자식으로 추가되거나, N이 G의 오른쪽 자식의 오른쪽 자식으로 추가되는 경우(P는 red, U는 black)
     • N이 G의 왼쪽 자식의 왼쪽 자식으로 추가되는 경우 Lotation을 수행하고 P와 G의 색상을 바꾼다

Deletion

• 삭제하는 노드가 red 노드면 삭제 끝
• 삭제하는 노드가 black 노드고 대체되는 자식 노드도 black 이면 자식 노드는 double black 노드로 마크해둔다
• 트리의 밸런스를 맞출 때 가장 주요한 일은 double black 노드를 일반 black node로 바꾸는 것이다
• D: 삭제되는 노드, C: 선택된 D의 자식 노드
  1. D가 red 노드인 경우
     • 간단하게 D를 삭제
  2. D는 black 노드이고 C는 red 노드인 경우
     • D를 삭제
     • D 자리를 C로 대체
     • C를 black 노드로 바꿈
  3. D와 C가 모두 black 노드인 경우
     • D를 삭제하고 C로 대체
     • C를 N으로 이름을 바꿈
     • N을 double black 노드로 마크
       1. N이 새로운 root 노드일 때
          • double black을 single black으로 바꿈
       2. 형제노드 S가 red 노드일 때
          • P를 red 노드로, S를 black 노드로 바꾸고 rotation 수행
          • 규칙에 위배되는 경우, 해당 규칙을 따르기 위한 방법을 수행한다
       3. 부모 노드 P, 형제 노드 S, S의 자식 노드 S_L와 S_R이 모두 black 노드일 때
          • S를 red 노드로 바꾼다
          • double black을 P로 보낸다
          • 규칙에 위배되는 경우, 해당 규칙을 따르기 위한 방법을 수행한다
       4. 부모 노드 P는 red 노드고, 형제 노드 S, S의 자식 노드 S_L와 S_R이 black 노드일 때
          • P를 black 노드로, S를 red 노드로 바꾼다
       5. 형제 노드 S는 black, S의 자식 노드 중 N과 가까운 노드는 red 노드, 멀리 있는 자식 노드는 black 노드일 때
          • Rotation 수행
          • S의 자식 노드 중 N과 가까웠던 노드를 black 노드로, S를 red 노드로 바꾼다
          • 규칙에 위배되는 경우, 해당 규칙을 따르기 위한 방법을 수행한다
       6. 형제노드 S가 black 노드고, S의 자식 노드 중 N과 가까운 노드가 black 노드, 멀리 있는 자식 노드는 red 노드일 때,
          • Rotation 수행
          • P와 S의 색깔을 바꾼다
          • 멀리 있는 자식 노드를 black 노드로 바꾼다

AVL Tree vs. Red-Black Tree

• 유사점
  • 둘 다 binary search tree
  • 탐색, 삽입, 삭제에서 같은 규칙을 따른다
  • 둘 다 balanced tree지만, perfectly balanced는 아니다
  • 둘 다 균형을 맞추기 위해 rotation을 이용한다
• 차이점
  • AVL 트리는 균형을 판단하기 위해 balance factor를 이용하고 균형이 필요한 4가지 경우를 가지고 있다
  • Red-Black 트리는 주변 노드와 자체의 색상으로 균형을 판단하고, 균형이 필요한 많은 경우를 가지고 있다