이진트리 & 레드-블랙트리

"이진 탐색 트리는 기본적으로 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 커야한다." 를 전제로 한다.

BST(Binary Searching Tree) : 이진탐색트리

이진트리는 아래와 같은 규칙을 갖는다.

• 삽입
  • 삽입을 하기 전, 검색을 수행한다.
  • 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.
• 삭제
  • 자식노드가 없는 노드(리프 노드) 삭제
    • 해당 노드를 단순히 삭제한다.
  • 자식노드가 1개인 노드 삭제
    • 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.
  • 자식노드가 2개인 노드 삭제
    • 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽 서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
      
      

이진트리에서의 시간복잡도

이진 탐색트리의 경우 BST 데이터가 랜덤하게 배치되어있다고 가정했을 때, 평균 트리의 시간복잡도는 O(logn) 형태가 된다.

그러나, 아래와 같이 랜덤하게 배치된 BST의 경우 E를 검색하기 위해서는 결국 모든 Node들을 탐색해야 하는 문제가 생겨 최악의 경우 O(n)의 형태가 될 수 있다.

편향(unbalanced tree)

우선적으로, 최악의 시나리오가 O(n) 일 경우 좋은 알고리즘은 아니다.

위와 같은 형태가 발생할 수 있어 이를 이진탐색트리 불균형(unbalanced Binary tree) 라고 한다.

이를 위해서 고안된 트리가 RBT(Red Black Tree) 이다.

 

RBT(Red Black Tree) : 레드-블랙 트리

RBT는 BST 와는 다르게 BST 는 Worst Case 의 경우 시간복잡도가 O(n) 의 형태이지만 RBT는 Worst Case 경우에도 O(logn) 을 보장한다.

 

Red-black 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.

연관 배열이나 SET 등을 내부적으로 red-black 트리로 구현해 놓은 경우가 다수이다.

삽입 삭제시 O(log n) 만큼의 시간이 필요하다.

Red-Black 트리는 노드가 레드나 블랙인 색상 속성을 가지고 있는 이진 탐색 트리이다.

조건

• 이진탐색트리가 가지는 조건에 다음과 같은 추가적인 조건을 만족해야한다.
  • 노드는 레드 혹은 블랙 중의 하나이다.
  • 루트 노드는 블랙이다.
  • 모든 리프 노드들은 블랙이다.
  • 레드 노드의 자식노드 양족은 언제나 모두 블랙이다.
  • 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

위에 조건을 충족한 RBT의 형태

RB-TREE

RBT에서의 탐색, 삽입, 삭제

1) 탐색 

RBT 에서의 탐색은 기존 BST 탐색과 같은 방법으로 진행하며 크게 다른 부분은 없다.  기본적으로 RBT 는 BST 에서 나온 특수한 한 형태이므로 읽기 전용 동작의 구현을 변경하지 않아도 된다.

즉, 탐색은 BST 와 같은 동작으로 하게된다. 시간복잡도는 Worst Case 경우 O(logn) 은 충족한다.

이유는, 삽입과 삭제에서 BST와 다른 동작을 하게되므로 기본적으로 Balance 가 보장되는 구조를 지니고 있기 때문이다. 그래서 RBT를 자가균형 이진탐색트리 라고도 불리운다.

앞서 BST 에서 설명한 편향된 Unbalanced Binary Tree 에서 보여준 트리와 다르게 RBT 는 기본적으로 삽입과 삭제 처리에서 균형을 맞춰주는 기능을 가지고 있다.

 

이에 2가지 기능이 필요하다.

1. 트리회전
2. 색 변환

1-1) 트리회전

트리회전은 트리의 좌우 균형을 맞춰주기 위해 특정 조건에서 노드의 회전을 통해 균형을 맞춰주는 기능을 말한다.

회전의 기능 코드

 

// 오른쪽 회전
static void rotate_left(struct node *n)
{
    struct node *c = n->right;
    struct node *p = n->parent;
 
    if (c->left != NULL)
        c->left->parent = n;
 
    n->right = c->left;
    n->parent = c;
    c->left = n;
    c->parent = p;
 
    if (p != NULL) {
        if (p->left == n)
            p->left = c;
        else
            p->right = c;
    }
}
 
// 왼쪽 회전
static void rotate_right(struct node *n)
{
    struct node *c = n->left;
    struct node *p = n->parent;
 
    if (c->right != NULL)
        c->right->parent = n;
 
    n->left = c->right;
    n->parent = c;
    c->right = n;
    c->parent = p;
 
    if (p != NULL) {
        if (p->right == n)
            p->right = c;
        else
            p->left = c;
    }
}

1-2) 색 변환

색 변환은 RBT 의 조건중 하나인 

• 레드 노드의 자식노드 양족은 언제나 모두 블랙이다.

에 부합하기 위한 기능으로 부모노드와 자식노드는 둘 다 레드의 색을 가질 수 없다의 기능을 충족하기 위한 기능을 말한다.

 

그래서 각 노드들은 아래와 같은 추상적 개념을 가지고있다.

 

struct RBTNode
{
    struct RBTNode* parent;
    struct RBTNode* left;
    struct RBTNode* right;
 
    int data;
    enum Color color;
     
};

2) 삽입

• N : 삽입할 노드
• P : N의 부모 노드
• U : N의 삼촌 노드, P의 형제노드
• G : 조부모 노드

삽입은 총 5가지의 삽입 절차를 가지고 있다.

1. N 이라고 하는 새로운 노드가 트리의 시작(Root) 에 위치한다.
   1. 이 경우, 레드-블랙 트리의 첫 번째 속성(트리의 시작은 검은색이다)을 만족하기 위해서, N을 검은색으로 표시한다.
   2. 이 경우, 시작점으로부터 뻗어나가는 모든 경로에 검은색 노드를 하나 추가한 셈이 되기 때문에 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)은 여전히 유효하다.
2. 새로운 노드의 부모 노드 P가 검은색이라면, 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식 노드는 검은색이다)은 유효하다.
   1. 두 번째 경우에도 이 트리는 적절한 레드-블랙 트리이다.
   2. 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)도 별 문제가 없는데, 이는 새로운 노드 N은 두개의 검은색 노드를 leaf node로 가지고 있기 때문이다.
   3. 비록 N이 붉은색 노드라고 해도 N이 들어간 자리에 원래 위치했던 노드의 색이 검은색이었으므로, N의 자식 노드에게서 시작되는 경로들은 모두 같은 수의 검은색 노드를 가지게 되고, 결과적으로 다섯 번째 속성은 유지되게 된다.
3. 만약 부모 노드 P와 삼촌 노드 U가 모두 붉은색 노드라면, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)을 유지하기 위해서, P와 U를 모두 검은색으로 바꾸고 할아버지 노드 G를 붉은색으로 바꾼다.
   1. 붉은색 노드인 N은 검은색 부모 노드를 가지게 된다.
   2. 이번에는 할아버지 노드 G가 레드 블랙 트리의 두 번째 속성(root node는 검은색이다)이나 네 번째 속성(붉은색 노드의 두 자식 노드는 검은색이다)을 만족하지 않을 수 있다(네 번째 속성은 G의 부모 노드가 붉은색일 경우 만족하지 않는다).
   3. 이를 해결하기 위해서 G에 대해 지금까지 설명한 첫 번째 경우부터 세 번째 경우까지를 재귀적으로(recursively) 적용한다. 이 작업은 삽입 과정 중에 발생하는 유일한 재귀 호출(recursive call)이며, 회전(rotation) 작업을 하기 전에 적용해야 한다는 것에 주의한다.
4. 자식이 부모 왼쪽, 부모가 조부모 오른쪽일 경우 왼쪽 회전을 한다.
   1. 부모 노드였던 P를 다섯 번째 경우에서 처리하게 되는데, 이는 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식은 검은색 노드이다)을 아직 만족하지 않기 때문이다.
   2. 회전 작업은 몇몇 경로들이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)을 위반하지 않는다.
5. 자식이 부모 왼쪽, 부모가 조부모 왼쪽일 경우 오른쪽 회전을 한다.
   1. 회전의 결과 이전의 부모 노드였던 P는 새로운 노드 N과 할아버지 노드 G를 자식 노드로 갖는다,
   2. G가 이전에 검은색이었고, P는 붉은색일 수밖에 없기 때문에, P와 G의 색을 반대로 바꾸면 레드-블랙 트리의 네 번째 속성(붉은색 노드의 두 자식 노드는 검은색 노드이다)을 만족한다.
   3. 바뀌기 전에는 G가, 바뀐 후에는 P가 P, G, N중 유일한 검은색 노드이다.

3) 삭제

• N : 삽입할 노드
• P : N의 부모 노드
• U : N의 삼촌 노드, P의 형제노드
• G : 조부모 노드
• S : N의 형제 노드

삭제는 총 6가지의 삭제 절차를 가지고 있다

1. N 이 새로운 루트가 될때. 이 경우에는 더 할게 없다. 우리는 모든 경로에서 하나의 검은 노드를 삭제했고, 새로운 루트 노드는 검은색이므로 모든 특성이 보존된다.
2. S 가 빨강일 경우. P의 자식인 S가 빨강색이므로 P가 검은색임이 명확하다. 이 경우 P와 S의 색을 바꾸고, P에서 왼쪽으로 회전
   1.  S가 N의 할아버지 노드가 된다.
   2. 모든 경로에서의 검은 노드의 수가 같지 않으므로 아직 끝나지 않았다. 
   3. 이제 N이 검은색 형제노드와 붉은색 부모 노드 갖고 있으므로,  4, 5, 6 절차를 진행할 수 있다.
3. P, S, 그리고 S의 자식들이 검은색인 경우. 이 경우, 우리는 간단히 S를 빨강으로 칠하면 된다.
   1. S를 지나는 모든 경로들(N을 지나지 않는 경로)은 하나의 검은노드를 적게 갖고 있게 된다.
   2. N의 원래 부모노드를 삭제하는 과정에서 N을 지나는 모든 경로들은 하나의 검은 노드를 적게 갖게 되므로, 양쪽은 같은 수의 검은 노드를 갖게 된다
   3. P를 지나는 모든 경로들은 P를 지나지 않는 모든 경로에 대해 검은 노드를 한 개 적게 지니게 되므로, 특성 5(특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다.)를 위반하게 된다.
   4. 이를 바로잡기 위해서, 우리는 P에다 case 1부터 시작하는 Rebalancing 과정을 수행해야 한다.
4. S와 S의 자식들은 검은색이지만, P는 빨강인 경우. 이 경우, 우리는 단순히 S와 P의 색을 바꾸면 된다.
   1. 이는 S를 지나는 경로의 검은 노드 개수에 영향을 주지 않지만, N을 지나는 경로에 대해서는 검은 노드의 개수를 1개 증가시킨다.
   2. 이는 원래 삭제된 검은 노드의 개수를 보충해준다.
5. S가 검정, S의 왼쪽 자식이 빨강, S의 오른쪽 자식이 검정이며, N이 부모의 왼쪽 자식인 경우. 이 경우 우리는 S를 오른쪽으로 회전시켜서 S의 왼쪽 자식이 S의 부모노드이자 N의 새로운 형제 노드가 되도록 만든다.
   1. 우리는 S의 색을 부모 노드의 색깔과 바꾼다. 모든 경로는 여전히 같은 수의 검은 노드수를 가지나, 이제 N이 오른쪽에 붉은 노드를 자식으로 둔 검은색 형제노드를 갖게 되었으므로, 6번째 절차로 진행하면 된다.
   2. N이나 N의 부모노드는 이 변형에 아무런 영향을 받지 않는다.
6. S가 검정, S의 오른쪽 자식이 빨강이며, N 이 P의 왼쪽 자식인 경우. 이 경우 우리는 P를 왼쪽으로 회전해서, S가 P와 S의 오른쪽 자식노드의 부모 노드가 되게 한다.
   1. 우리는 P와 S의 색을 바꾸고, S의 오른쪽 자식노드를 검은색으로 만든다.
   2. N은 이제 하나의 추가적인 검은 조상 노드를 가지게 된다:P가 검은색으로 바뀌든가, 아니면 P가 검은색이었고 S가 검은색 할아버지 노드로 추가되었든지. 그러므로, N을 지나는 경로는 하나의 추가적인 검은 노드를 갖게 된다.

 

삽입 절차와 삭제절차는 (https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC) 문서 상 코드로 더 명확하게 알 수 있습니다.

 

참조 

• https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
• https://www.cs.usfca.edu/~galles/visualization/RedBlack.html