#9 트리(Tree) 4 - 레드블랙 트리(Red-Black Tree)

1. 레드블랙 트리(Red-Black Tree)

 레드블랙 트리는 지난번에 다루었던 AVL 트리와 같은 자가 균형 이진 탐색 트리의 일종이다. 레드블랙 트리는

다음과 같은 조건을 만족한다.

• 모든 노드는 색을 가지고있으며 색은 붉은색 또는 검은색 중 하나이다.
• 루트 노드는 검은색이다.
• 모든 리프 노드(NIL)는 검은색이다.
• 붉은색 노드의 자식 노드는 검은색이다. => 붉은색 노드는 연속해서 나올 수 없다.
• 모든 리프노드에서 Black Depth가 같다. 
  => 리프 노드에서 루트 노드까지 거슬러올라가며 만나는 블랙노드의 갯수가 모두 동일하다.

위 조건들을 만족함으로서 레드블랙 트리는 아주 중요한 특성을 가지게 된다. 모든 리프노드의 Black Depth가

같다면 그 사이에 붉은색 노드를 아무리 많이 끼워넣는다 해도 붉은색 노드는 연속으로 나올 수 없기 때문에

넣을 수 있는 붉은색 노드의 갯수는 (검은색 노드의 갯수 - 1) 개가 한계이다. 즉, 모든 리프노드의 깊이는

가장 얕은 리프노드의 깊이의 두 배를 넘을 수 없다.  이 특성 덕분에 AVL트리만큼은 아니어도 레드 블랙 트리는

상당히 균형잡힌 이진 탐색 트리가 된다.

 

2. 레드블랙 트리의 특징

• AVL 트리와 마찬가지로 어떤 경우에도 삽입, 삭제, 검색에 O(logN)의 시간복잡도를 보장한다.
• 매 삽입/삭제마다 최악의 경우 많은 회전 연산이 발생하는 AVL 트리에 비해 삽입/삭제에 걸리는 시간이
  비교적 적다.
• 많은 프로그래밍 언어의 해시맵이나 집합 등의 라이브러리를 구현하는데에 레드블랙 트리가 활용된다.

 

3. 삽입/삭제시 Double-Red 처리 알고리즘

 레드블랙 트리는 삽입, 삭제 결과 발생한 규칙의 어긋남을 회전과 색변경을 통해 바로잡는다.   회전의 경우 AVL 트리에

사용했던 LL회전(right_rotation), RR회전(left_rotation)을 그대로 사용한다.  

 

① 삽입

 삽입 연산의 경우 문제의 발생여부를 아는것은 굉장히 간단하다. 삽입되는 노드는 기본적으로 붉은색 노드이기 때문에

삽입된 노드의 부모노드도 붉은색이라면 Double-Red 문제가 발생한다. 그리고 이 상태에서 문제해결은 삽입된 노드의
삼촌노드(부모 노드의 형제노드)의 색에 따라 두 가지 케이스로 나누어 진행된다.

• Recoloring
  • 삼촌노드의 색이 붉은색일 경우 발생
  • 삼촌노드와 부모노드의 색을 모두 검은색으로 변경해준 다음 조부모노드(부모노드의 부모노드)의 색을 붉은색으로 변경해준다. 부모노드와 삼촌노드쪽 모두 검은색노드가 하나 늘어난 동시에 조부모노드가 붉은색이 되며
    일괄적으로 하나씩 줄었기 때문에 balck depth에는 영향을 주지않는다.
  • 다만 조부모 노드가 붉은색으로 바뀌면서 추가적으로 Double-Red 문제가 발생할 수 있기 때문에 조부모노드를
    새로 삽입한 노드로 취급하여 DoubleRed 처리를 재차 실행한다.
  • 즉, Recoloring은 한번 수행하고나서도 추가작업이 필요할 수 있다.
• Restructuring
  • 삼촌노드의 색이 검은색일 경우 발생
  • 조부모노드 - 부모노드 - 삽입된 노드의 형태에 따라 회전 연산을 수행
  • LL 상태라면 조부모노드에 대해 right_rotation 수행
    RR 상태라면 조부모노드에 대해 left_rotation 수행
    LR 상태라면 부모노드에 대해 left_rotation 을 수행한 뒤 조부모노드에 대해 right_rotation 수행
    RL 상태라면 부모노드에 대해 right_rotation 을 수행한 뒤 조부모노드에 대해 left_rotation 수행
  • Restructuring 의 경우 이 작업만으로 더이상의 추가적인 Double-Red 문제가 발생하지 않기 때문에
    여기서 작업이 종료된다.
• 모든 작업이 종료되면 루트노드를 검은색으로 바꿔준다.

 

② 삭제

 삭제연산은 조금더 복잡하다. 일반적인 이진탐색의 삭제연산의 경우 삭제할 노드의 좌측 서브트리중 최댓값 또는 
우측 서브트리중 최솟값을 가져와 삭제된 노드를 대체하는 형태로 이뤄진다.  레드블랙트리는 그렇게 삭제가 이뤄진 후 

규칙을 유지하기 위해 추가작업을 수행한다.  먼저 삭제된 노드 부분에는 문제가 발생하지 않는다.  삭제된 노드를
대체할 후임자 노드의 색을 삭제된 노드의 색으로 바꿔주면 되기 때문이다.  문제는 후임자 노드의 자리에서 발생한다.

삭제된 노드가 리프노드일 경우에는 삭제된 노드 자리를 대체한 NIL 노드가 C 노드가 되고 그 부모노드가 P 노드가

된다. C노드의 부모노드가 없는 경우에는 트리가 비어있는 상태이기 때문에 그대로 삭제연산을 종료한다.)

• 후임자 노드가 붉은색일 경우
  • 후임자 노드가 붉은색이라면 사라지더라도 규칙에 아무 영향을 주지않는다.
• 후임자 노드가 검은색이고 후임자 노드의 한쪽 자식노드가 붉은색인 경우
  • 후임자 노드가 검은색이어도 후임자 노드의 자식노드가 붉은색이라면 그 노드를 검은색으로 바꿔주면
    문제가 간단히 해결된다.
    
    
• 후임자 노드와 후임자 노드의 한쪽 자식노드 모두 검은색인 경우
  • 이 경우가 가장 복잡한 상황이다. 이 경우 후임자 노드의 한쪽 자식노드 C를 기준으로 그 부모노드 P,
    형제노드 S, 가까운 조카노드 N1 과 먼 조카노드 N2 의 상태를 기준으로 다섯가지 케이스로 나누어
    해결해나가야 한다. 여기서는 C가 P의 좌측 자식노드이고 S가 P의 우측 자식노드인 경우를 상정하여
    설명한다. 만약 반대로 C가 P의 우측 자식노드인 경우에는 회전 방향을 반대로 해야한다.
    
    
  • 케이스 1. P는 붉은색, S, N1, N2는 모두 검은색인 경우
    • P와 S의 색을 서로 맞바꾸는 것만으로 더이상의 추가작업 없이 간단히 해결할 수 있다.
    • 다섯가지 케이스중 가장 간단한 케이스이다.
      
      
  • 케이스 2. P, S, N1, N2 가 모두 검은색인 경우
    • S의 색을 붉은색으로 변경하는 것으로 C쪽과 S쪽 모두 검은색 노드가 하나씩 부족하도록 한다.
    • 결과적으로 부모노드 P 기준으로 검은색노드가 하나 부족하게되어 P 노드에 문제를 떠넘길 수 있다.
    • C 를 P로, P를 P의 부모노드로 재설정하여 다시한번 해당하는 케이스를 찾아 작업을 진행하도록 한다
      
      
  • 케이스 3. P, N1, N2는 검은색이고 S는 붉은색인 경우
    • P를 기준으로 left_rotation 을 수행한 뒤 P와 S의 색을 맞바꾼다. P의 색이 바뀌었기 때문에 바뀐 색상에
      따라 다시한번 해당 케이스를 찾아 작업을 진행하도록 한다.
      
      
  • 케이스 4. P의 색은 무관, S가 검은색이고 먼 조카노드 N2가 붉은색인 경우
    • P를 기준으로 left_rotation 을 수행한 뒤 P와 S의 색을 맞바꾼 뒤 먼 조카노드 N2를 검은색으로 변경한다.
      
      
  • 케이스 5. P의 색은 무관, S가 검은색이고 가까운 조카노드 N1은 붉은색, 먼 조카노드 N2는 검은색인 경우
    • S를 기준으로 right_rotation 을 수행한 뒤 가까운 조카노드 N1과 S의 색을 맞바꾼다.
    • 이 결과 케이스 4와 동일한 형태가 되니 계속해서 작업을 진행한다.
      
      
  • 위 작업을 케이스 1 또는 케이스 4 작업을 수행하여 추가작업이 필요없어지거나 C가 루트노드에 도달하여
    parent 노드가 존재하지 않을 때 까지 반복한다.
    
    
  • 모든 작업이 끝나면 루트노드를 검은색으로 바꿔준다.

 

글을 작성하면서 레드블랙트리를 직접 구현해보았지만 적은 양의 데이터로 하나하나 삽입, 삭제를 수행했을 때는

정상적으로 작동하는 것으로 보였지만 대량의 데이터를 삽입/삭제 해보니 삭제연산중에 문제가 있어 오류가 발생하는

경우가 나타났다. 나중에 시간이 되면 처음부터 다시한번 구현해볼 필요가 있을 것 같다.

 

추가) 2021.10.13

 좀더 알아보니 모든 노드가 좌우 자식노드로 검은색 NIL 노드를 가지도록 설계해야 구현이 쉬울 것으로 보여 설계를

처음부터 다시해보았다. 노드를 삽입할 때 삽입위치인 NIL 노드에 key값과 색상을 설정하고 좌우에 NIL 노드를 생성하여 붙이도록 했더니 삭제기능도 문제없이 작동하였다.