Red Black Tree - 소스 코드 해석-

 

목차

 

자료 출처 및 참고 링크

강의 자료 출처 : https://www.youtube.com/c/DdmixBlogspot/featured

Jake Lee

 

강의 자료 노트: https://bdbest.tistory.com/150

 

소스 코드 링크: https://github.com/leejaku17/cppalgo_2002/blob/master/Week3/Search/RBTreeMap.h#L49

 

소스 코드 링크의 코드를 참고하여 구현하였습니다.

 

 

1. rbtree.h, 헤더 파일

 

#ifndef RBTREE_H_
#define RBTREE_H_

#include <stddef.h>

typedef enum
{
  RBTREE_RED,
  RBTREE_BLACK
} color_t;

typedef int key_t;

typedef struct node_t
{
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;

typedef struct
{
  node_t *root;
} rbtree;

rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);

node_t *rbtree_insert(rbtree *, const key_t);
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);
int rbtree_erase(rbtree *, node_t *);

int rbtree_to_array(const rbtree *, key_t *, const size_t);

#endif // RBTREE_H_

 

 

 

 

 

2. rbtree.c ( 기초 코드 )

 

#include "rbtree.h"
#include <malloc.h>

//test case assert 통과를 위해
node_t *head_node;
int node_count;

void *head_node_to_t_root(rbtree *t)
{
  t->root = head_node->left;
}

//rbtree_to_array로 출력된 배열을 정렬하기 위한 함수

static int comp(const void *p1, const void *p2)
{
  const key_t *e1 = (const key_t *)p1;
  const key_t *e2 = (const key_t *)p2;
  if (*e1 < *e2)
  {
    return -1;
  }
  else if (*e1 > *e2)
  {
    return 1;
  }
  else
  {
    return 0;
  }
};

// 다른 방식의 정렬
// int compare(const void *a, const void *b)
// {
//   return (*(int *)a - *(int *)b);
// }
//여기까지

rbtree *new_rbtree(void)
{
  rbtree *p = (rbtree *)calloc(sizeof(rbtree), 1);
  return p;
}

 

 

 

 

 

3. insert 삽입 함수

 

node_t *rbtree_insert(rbtree *t, const key_t key)
{
  // TODO: implement insert

  // 첫 삽입
  if (t->root == NULL)
  {
    // 루트 만들기:
    node_t *temp;
    temp = malloc(sizeof(node_t));
    t->root = temp;
    t->root->key = key;
    t->root->color = RBTREE_BLACK;
    t->root->left = t->root->right = t->root->parent = NULL;
    node_count = 1;

    //headnode 생성
    head_node = malloc(sizeof(node_t));
    head_node->left = t->root;
    head_node->right = head_node->parent = NULL;
    head_node->color = RBTREE_BLACK;
    // t->root->parent = head_node;

    return t->root;
  }

  //두번째+ 삽입
  // n이 현재 노드를 지칭.
  node_t *n, *p, *gp, *ggp;
  ggp = gp = p = (node_t *)head_node;
  n = head_node->left;

  while (n)
  {
  
  	// 중복 방지를 위해
    if (key == n->key)
    {
      head_node_to_t_root(t);
      return 0;
    }
    
	// 상향 색변환 가능한 상황, 자식 노드 두개가 빨강이고 나는 검정일때
    if (n->left && n->right && n->left->color == RBTREE_RED && n->right->color == RBTREE_RED)
    {
      
      n->color = RBTREE_RED;
      n->left->color = n->right->color = RBTREE_BLACK;
	  
      // 색 변환 이후의 경우에만 원칙 위배 상황이 발생함. 이를 해소하기 위해 회전이 필요한지 체크.
      
      // 빨강이 연속되기에 회전 필요
      if (p->color == RBTREE_RED)
      {
      
        gp->color = RBTREE_RED;
        
        //이중 회전이 필요한 경우
        if ((key > gp->key) != (key > p->key))
          p = _Rotate(key, gp, t);
        n = _Rotate(key, ggp, t);
        n->color = RBTREE_BLACK;
      }

      // 루트는 언제나 검정
      head_node->left->color = RBTREE_BLACK;
    }

    //gp, p 등등 업데이트
    ggp = gp;
    gp = p;
    p = n;
    
    // 삽입하려는 key 값에 따라 트리 좌우 결정
    if (key > n->key)
      n = n->right;
    else
      n = n->left;
  }

// while문을 탈출 할 경우, NULL leaf에 도달했다는 뜻

// key 값을 배정할 노드 생성 후 배정
  node_t *temp;
  temp = malloc(sizeof(node_t));
  temp->key = key;
  temp->left = temp->right = NULL;
  temp->parent = p;
  temp->color = RBTREE_RED;
  node_count++;

//부모 노드와 연결
  if (key > p->key && p != head_node)
    p->right = temp;
  else
    p->left = temp;

  //부모가 빨강이면 한번 더 회전 / 삽입 노드는 빨강이기 때문;
  if (p->color == RBTREE_RED)
  {
  
    gp->color = RBTREE_RED;
    if ((key > gp->key) != (key > p->key))
      p = _Rotate(key, gp, t);
    temp = _Rotate(key, ggp, t);
    temp->color = RBTREE_BLACK;
    
  }

  //뿌리는 검정으로
  head_node->left->color = RBTREE_BLACK;

  head_node_to_t_root(t);
  return head_node->left;
}

 

 

1. 노드는 Leaf 아래에 삽입한다.

2. 삽입 되는 노드는 빨강이다.

 

3. 이를 위해선 leaf 노드가 검정이여야 한다.

4. 그렇기에 상향 색변환 (부모를 빨강으로, 자식 두개를 검정으로) 이 가능할 경우 진행하며 하향 탐색한다. 

4.1 상향 색변환 이 실행 되고, 빨강 노드가 연속되는 상황이 생길 경우, 회전을 통해 부모노드를 검정으로 만든다.

4.2 상향 색변환 없이 회전이 진행되는 일은 없다. 상향 색변환이 진행되어야 균형이 깨지는 경우가 발생한다.

 

5. 하양 탐색 끝에 n=NULL일 때 node를 생성하고 p와 연결한다.

5.1 p가 빨강 일 경우, 회전을 통해 빨강 연속을 해결한다.

 

 

4. rotate 회전 함수

 

 

node_t *_Rotate(const key_t key, node_t *pivot, rbtree *t)
{
  node_t *child, *gchild;

 // pivot을 기준으로 올바른 child에 선택           
 //head_node->left 가 root노드 이기에
  if ((key > pivot->key || key == pivot->key) && pivot != head_node)
    child = (node_t *)pivot->right;
  else
    child = (node_t *)pivot->left;      // pivot이 head_node 인 경우
  
  
  //회전 방향을 정하기
  //좌회전
  if (key > child->key || key == child->key)
  {
    gchild = (node_t *)child->right;
    child->right = gchild->left;
    gchild->left = (node_t *)child;
  }
  
  //우회전
  else
  {
    gchild = (node_t *)child->left;
    child->left = gchild->right;
    gchild->right = (node_t *)child;
  }
  
  if ((key > pivot->key || key == pivot->key) && pivot != head_node)
    pivot->right = gchild;
  else
    pivot->left = gchild;

  return gchild;
}

 

 

단일 회전

참고 자료:

 

오른쪽 그림 설명:

insert 기준 : A = ggp, C = gp, E = p, G = n

rotate 기준 : A = pivot , C = child, E = gchild

 

1. n이 G 일 때(도착했을때) 상향 색변환 

 

----> (보라색 화살표)

 

2. p 의 색이 빨강임으로 연속되는 상황.

 

---->

 

3. 이를 해소하기위해 상위 조건으로 회전시켜 부모 노드 p가 검정이 되게 전환. E 가 n으로 바뀜.

 A = ggp, C = gp, E = p, E = n 인 상태

 

의문 해소:
E 가 n으로 바뀜에 따라 p = n 인 상황이 만들어진다. 이게 유지가 되면 문제가 생기는데, 이는 n이 원래 내려갈 예정이던 위치인 F, H 노드에 하향 탐색을 통해 도달하는 경우, gp, p, n 까지 본래의 관계로 돌아오고 그 다음으로, F, H 노드는 원래 빨강이었기에 빨강 자식 노드가 없음으로  F, H의 자식 노드까지 탐색을 하게 되면 자연스럽게 ggp 까지 정상적인 위치를 가르키게 된다!

 

note :
pivot이 왼쪽인지 오른쪽인지는 회전에 상관 없다. 회전 방향은 key 인자가 결정한다. pivot이 child와 gchild를 결정한다.

 

이중 회전

참고 자료:

 //from insert 함수     //빨강 노드가 연속된다
      if (p->color == RBTREE_RED)
      {
      
        gp->color = RBTREE_RED;
        
        //이중 회전이 필요한 경우
        if ((key > gp->key) != (key > p->key))
          p = _Rotate(key, gp, t);
          
        n = _Rotate(key, ggp, t);
        
        n->color = RBTREE_BLACK;
        
      }

.

 

오른쪽 그림 설명 : A = ggp, C = gp, G = p, E = n

 

 

1. 탐색 중 E 도달,  E = n 이 됨. 상향 색변환 가능하기에 실행

 

----> (보라색 화살표)

 

2. 상향 색변환 후 , E - G 빨강 노드 연속, 회전 필요, 우회전 실행 ,

C = gp = pivot , E = gchild = p 로 설정 (바로 위 코드 참조)

 

---->

 

3. G - E  여전히 빨강 노드 연속, 좌회전 실행

A = ggp = pivot, C = child , E = gchild = n

 

---->

 

4. 색 변환 후 마무리. 

A = ggp, C = gp, E = p, E = n 인 상태

 

위 단일 회전과 동일하게 D, F노드는 원래 빨강 노드 였음으로 D, F의 자식 노드 까지 탐색 ( 깊이 3 ) 할 경우 ggp, gp, p, n 이 E, C, D or F, 자식 노드, 이렇게 정렬 된다.

 

 

5. erase 삭제 함수

 

 

int rbtree_erase(rbtree *t, node_t *p)
{
  // TODO: implement erase
  node_t *delgp, *delp, *del, *sib;

  int value = p->key;

  //루트 노드부터 탐색 시작
  delgp = delp = (node_t *)head_node;
  del = head_node->left;
  sib = 0;

  //leaf노드까지 탐색
  while (!_IsLeafNode(del))
  {
  
	// 첫번째 조건문. 
    / /하향 탐색 경로로 빨간 노드 옮기기, 부모노드를 빨강으로 만들기 위해!
    
    // del 빨강이 아니고
    if (del->color != RBTREE_RED)
    {
      // sib가 빨강이라면, 회전진행, 아니면 그냥 통과.
      if (_RedAsParent(delgp, delp, sib, t))
      {
      
      // RedAsParent에서 회전이 진행되면 delgp 위치에 sib가 가기 때문에
        delgp = sib;
        if (del->key > delp->key || del->key == delp->key)
          sib = delp->left;
        else
          sib = delp->right;
      }
    }

    // 첫번째 조건문을 통과했기에 부모 delp는 반드시 빨강노드.

	// 두번째 조건문.
    // 형제에게서 빌리기, 형제와 결합하기 

    
    // del이 루트 노드가 아니고, del이 2노드라면
    if (del != head_node->left && _Is2Node(del))
    {
      
      // _Borrowkey 가 끝가지 진행되지 않았을 경우, 형제와 결합하기 진행.
      if (!_BorrowKey(delgp, delp, del, sib, t))
        _BindNode(delp);
    }

	// 세번째 조건문
    if (value == del->key)
      value = _Swapkey(del);

	//변수 값 업데이트
    delgp = delp;
    delp = del;
    if (value > del->key || value == del->key)
    {
      //swap key로 인해 같은 값이 나올수 있음.
      //In order successor을 사용하기 때문에 오른쪽으로
      sib = del->left;
      del = del->right;
    }
    else
    {
      sib = del->right;
      del = del->left;
    }
    
    //while문 한바퀴 
  }


  // while 종료, 즉 leaf 노드에 도달

  // 삭제전 마지막 정렬 1
  if (del->color != RBTREE_RED)
  {
    if (_RedAsParent(delgp, delp, sib, t))
    {
      // delgp 와 sib 의 위치가 변했다 새로 수정;
      delgp = sib;
      if (del->key > delp->key || del->key == delp->key)
        sib = del->left;
      else
        sib = delp->right;
    }
  }
  
  // 삭제전 마지막 정렬 2
  if (del != head_node->left && _Is2Node(del))
  {
    if (!_BorrowKey(delgp, delp, del, sib, t))
      _BindNode(delp);
  }
  
  //삭제 진행
  if (_DelLeafNode(value, delp, del, t))
  {
    node_count--;
    head_node_to_t_root(t);
    return 1;
  }
  else
  {
    head_node_to_t_root(t);
    return 0;
  }
}

 

참고 자료:

원칙 1 (_DelLeafNode)

- Leaf 3-4 노드의 (check by _IsLeafNode) 삭제는 Trivial 하다.

이 원칙을 위해 하향 탐색을 진행하며 원칙 2, 3을 적용 시킨다. 결과적으로 leaf 노드에 도달했을때 trivial한 상태가 됌.

 

원칙 2 (_RedAsParent)

- 3 노드의 등가 표현 중 하향 탐색 경로 쪽으로 빨간 노드가 위치하도록 바꾼다. 

하향 색변환(  자식 검검 부모 빨일 때 자식 빨빨 부모 검) 을 위해 지속적으로 옮겨준다.

2-3-4 트리 형태로 봤을 때에는 아무 변화가 없는 전환이다. - 균형을 깨지 않는다

 

원칙 3 (_Borrowkey, _BindNode)

- 삭제키를 찾는 하향탐색 중에 2노드를 (check by _Is2Node) 3-4 노드로 부풀려야 한다.

균형 트리에서 삭제할 노드가 있다는 뜻은, 곧 균형이 깨진다는 뜻. borrow 키를 실행 할 경우, 삭제할 노드가 있는 방향으로 깊이가 한단계 깊어진다.

 

원칙 4 (_SwapKey)

내부노드의 삭제는 In-Order Successor (Predecessor)와 바꿔치기 한 다음 leaf 3-4 노드의 삭제문제로 돌린다.

 

 

 

6. erase 삭제 함수 구현을 위한 내부 함수들

 

1. _IsLeafNode
2. _RedAsParent
3. _Is2Node
4. _BorrowKey
5. _BindNode
6. _Swapkey
7. _DelLeafNode

 

 

1. _IsLeafNode()

// 삭제 함수에 들어가는 함수 1
int _IsLeafNode(const node_t *p)
{
  if (p == NULL)
    return 0;
    
 //leaf 노드인 조건. 
 //p 노드 기준, 좌우가 NULL or 자식이 빨강이고, 손자가 없을 때
  if ((p->left == NULL || (p->left && p->left->color == RBTREE_RED && !p->left->left && !p->left->right)) 
  && (p->right == NULL || (p->right && p->right->color == RBTREE_RED && !p->right->left && !p->right->right)))
    return 1;
    
  else
    return 0;
}

 

원칙 1에 부합하는지 검사하는 함수

 

insert 함수에서 while 문 조건으로 n이 NULL일 때까지 진행된 것처럼,

erase 에서는 while문 조건으로 _IsLeafNode가 1을 반환 할 때까지, 즉 p 노드가 leaf 노드일 때까지 진행된다.

 

3-4 leaf 노드 형태:

 

 

 

2. _RedAsParrent()

// 삭제 함수에 들어가는 함수 2
int _RedAsParent(node_t *delgp, node_t *delp, node_t *sib, rbtree *t)
{
  if (sib == NULL || sib->color != RBTREE_RED)
    return 0;
  _Rotate(sib->key, delgp, t);
  sib->color = RBTREE_BLACK;
  delp->color = RBTREE_RED;
  return 1;
}

del 노드의 부모 노드, delp 의 색이 Black 일 경우, _RedAsParent 함수가 실행된다.

 

이 함수는 형제 노드 sib가 빨강일 경우 회전을 통해 delp를 빨강 노드로 만들어준다.

 

이를 위해 첫 조건문이 이를 검증한다. black일 경우 옮길 레드 노드가 없음으로 탈출한다.

 

 

회전이 진행 될 경우,

ggp = delgp , gp = delp , p= sib 인 상태로 회전이 진행된다.

이 경우 delgp만 sib으로 변경되고 (erase 함수 참조) del, delp는 변경되지는 않는다. 

(insert 함수에서는 n을 sib으로 변경하고 하향 탐색을 하며 ggp gp 등의 원래 관계를 회복한다.)

 

 

 

 

3. _Is2Node()

// 삭제 함수에 들어가는 함수 3
int _Is2Node(const node_t *p)
{
  if (p == NULL)
    return 0;
  if (p->color == RBTREE_RED)
    return 0;
  if ((p->left == NULL && p->right == NULL) || (p->left == RBTREE_BLACK && p->right == RBTREE_BLACK))
    return 1;
  else
    return 0;
}

2노드인지 검증하고 리턴한다.

 

2 노드의 형태: 

 

 

 

4. _BorrowKey()

// 삭제 함수에 들어가는 함수 4
int _BorrowKey(node_t *delgp, node_t *delp, node_t *del, node_t *sib, rbtree *t)
{
  node_t *sibrc;

  //조건 1
  //sib 가 2노드 일 경우, sibrc가 빨강일 수가 없으니 탈출
  if (_Is2Node(sib))
    return 0;

  // 조건 2
  // del이 sib의 왼쪽인지 오른쪽인지 판별 후 빨강 노드인 sibrc를 찾아 포인터 배정.
  if (del->key > sib->key)
  {
    if (sib->left && sib->left->color == RBTREE_RED)
      sibrc = sib->left;
    else
      sibrc = sib->right;
  }
  else
  {
    if (sib->right && sib->right->color == RBTREE_RED)
      sibrc = sib->right;
    else
      sibrc = sib->left;
  }

  //조건 3
  //그냥 회전인지 이중 회전인지
  if ((delp->key > sib->key) != (sib->key > sibrc->key))
  {
    //이중회전
    _Rotate(sibrc->key, delp, t);
    _Rotate(sibrc->key, delgp, t);
    sib->color = RBTREE_BLACK;
    sibrc->color = RBTREE_RED;
  }
  else
  {
    //단일 회전
    _Rotate(sib->key, delgp, t);
    sib->color = RBTREE_RED;
    sibrc->color = RBTREE_BLACK;
  }

  //변경된 상황에 맞는 색상 입히기
  del->color = RBTREE_RED;
  delp->color = RBTREE_BLACK;

  //루트 노드가 빨강으로 바뀌었으면 검정으로 바꾸고 종료.
  if (head_node->left->color == RBTREE_RED)
    head_node->left->color = RBTREE_BLACK;
  return 1;
}

 

 

상위 조건을 모두 통과했을 경우, 아래 그림 중 하나인 상황이 되어 있다.

그림에서 보듯이 회전을 진행한다.

 

단일 회전은 delgp 위치에 sib, 이중 회전은 delgp 위치에 sibrc가 올라가지만 이번엔 RedAsParent() 함수 때처럼 delgp를 업데이트 하지 않는다.

 

그 이유는 더이상 회전을 진행할 일이 없기 때문에 하향 탐색으로 다음으로 내려가기 때문이다. 

delgp=delp; delp = del;을 통해 원래 관계를 회복한다.  

 

 

 

5. _BindNode()

// 삭제 함수에 들어가는 함수 5
// 상향 색변환 / 형제와 결합
void _BindNode(node_t *delp)
{
  delp->color = RBTREE_BLACK;
  delp->left->color = RBTREE_RED;
  delp->right->color = RBTREE_RED;
}

상향 색변환이다.

 

 

 

 

 

6. _Swapkey()

 

// 삭제 함수에 들어가는 함수 6
key_t _Swapkey(node_t *del)
{
  node_t *cdd;
  cdd = del->right;
  while (cdd->left)
    cdd = cdd->left;
  del->key = cdd->key;
  return cdd->key;
}

 

삭제할 노드의 위치가 leaf가 아니라 내부 일 경우, 현 위치에서 오른쪽 서브트리에서 가장 왼쪽 노드로 대체키를 설정해 그림의 경우 D를 삭제하는 문제에서 leaf 노드에 있는 E노드를 삭제하는 문제로 변경 시킨다.

 

삭제할 값을 swapkey 에서 return 시키고 erase 함수에서 삭제할 값을 담고 있는 변수 value에 담아준다.

 

 

 

 

 

 

7. _DelLeafNode()

// 삭제 함수에 들어가는 함수 7
int _DelLeafNode(const key_t key, node_t *delp, node_t *del, rbtree *t)
{
  //첫번쨰 if문
  if (key == del->key && !del->left && !del->right)
  {
    // red leaf 나 black leaf 인 경우
    free(del);
    if ((key > delp->key || key == delp->key) && delp != head_node)
      delp->right = NULL;
    else
      delp->left = NULL;
    return 1;
  }
  else if (key == del->key) //black 노드인 경우
  {
    node_t *ret;
    if (del->left)
    {
      del->left->right = del->right;
      ret = del->left;
      ret->color = RBTREE_BLACK;
      free(del);
    }
    else if (del->right)
    {
      del->right->left = del->left;
      ret = del->right;
      ret->color = RBTREE_BLACK;
      free(del);
    }
    if ((ret->key > delp->key || ret->key == delp->key) && delp != head_node)
      delp->right = ret;
    else
      delp->left = ret;

    return 0;
  }
  else if (del->left && key == del->left->key)
  {
    free(del->left);
    del->left = NULL;
    return 1;
  }
  else if (del->right && key == del->right->key)
  {
    free(del->right);
    del->right = NULL;
    return 1;
  }
  else
  {
    return 0;
  }
}

 

 

 

 

 

 

7. delete 트리 초기화 함수

 

 

void delete_rbtree(rbtree *t)
{
  // TODO: reclaim the tree nodes's memory
  remove_subtree(t->root);
  if (head_node)
  {
    free(head_node);
  }

  node_count = 0;
  free(t);
}

void remove_subtree(node_t *node)
{
  if (node != NULL)
  {
    remove_subtree(node->left);
    remove_subtree(node->right);
    free(node);
    // return;
  }
  // return;
}

 

 

재귀적으로 구성해 가장 아래 왼쪽 부터 차례대로 free를 진행해 (중위순행) 놓치는 노드가 없게 설정했다.

 

 

 

 

 

 

8. find, min, max 탐색 함수

node_t *rbtree_find(const rbtree *t, const key_t key)
{
  // TODO: implement find
  node_t *s;

  s = head_node->left;
  while (s && !(key == s->key))
  {
    if (key > s->key)
      s = s->right;
    else
      s = s->left;
  }
  if (s == 0)
  //찾을 수 없는 경우
    return 0;
    
  // 찾았을 경우 
  return s;
}

node_t *rbtree_min(const rbtree *t)
{
  // TODO: implement find
  node_t *s;

  s = head_node->left;
  while (s && s->left)
  {
    s = s->left;
  }

  // printf("최소 값 찾았다! : %d\n", s->key);

  return s;
}

node_t *rbtree_max(const rbtree *t)
{
  // TODO: implement find
  node_t *s;

  s = head_node->left;
  while (s && s->right)
  {
    s = s->right;
  }

  // printf("최대 값 찾았다! : %d\n", s->key);

  return s;
}

 

RBtree 성질에 따라 min max는 좌 우 끝 노드까지 탐색하기만 하면 된다. find의 경우 그것을 조합하면 된다.

 

 

 

 

 

 

 

 

 

9. rbtree to array 트리 to 배열 함수

 

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
  // TODO: implement to_array
  int i = 0;
  add_to_array(head_node->left, arr, i);
  
  // 트리 초기화처럼 아래부터 배열에 저장할 수 잇으면 좋겠지만, 실패해
  // 모든 노드를 우선 담은 수 순서대로 정렬했다.
  qsort((void *)arr, n, sizeof(key_t), comp);
  return 0;
}

int add_to_array(node_t *node, key_t *arr, int i)
{
  if (node == NULL)
    return i;

  arr[i] = node->key;
  i++;

  if (node->left != NULL)
    i = add_to_array(node->left, arr, i);
  if (node->right != NULL)
    i = add_to_array(node->right, arr, i);

  return i;
}

 

중위 순행을 통해 오름차순으로 바로 넣는 방법은 아직 구현하지 못했다.

 

 

 

 

 

 

 

 

 

고생하셨습니다.