👩🏼‍💻TIL : 16. 🎄🎄RED-BLACK 트리를 구현하자🎄🎄

00. Red-Black트리란?

쨔자잔......레드블랙트리 완성

• 레드-블랙트리는 자기균형 이진탐색트리로서, 각 노드당 한 비트의 추가 기억 공간을 가진다.
• 비트는 노드의 색깔을 나타내는데, RED나 BLACK이 될 수 있다. 
• 값을 넣으면 트리가 근사적으로 균형을 이룬 트리가 되는 것이 특징이다.
• Red-Black트리는 5가지 특성을 만족하는 이진 검색 트리를 레드 블랙 트리라고 한다.
• 만들기 힘든 레드블랙트리 구경이라도 하자 : https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

 

   (1) Red-Black트리는 5가지 특성

      👉 모든 노드는 적색이거나 흑색이다. 

      👉 루트는 흑색이다.

      👉 모든 리프는 흑색이다.

      👉 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
        (레드 노드는 연달아 나타날 수 없다. 블랙 노드만이 레드노드의 부모 노드가 될 수 있다.)

      👉  노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

 

   (2) Red-Black 트리는 언제 사용할 수 있을까?

 

• Red-Black는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.
• 삽입, 삭제, 검색 시 최악의 경우에서의 시간복잡도가 트리의 높이에 따라 결정되기 때문에 보통의 이진탐색트리에 비해 효율적이다.
• 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐 아니라, 일정 실행 시간을 보장하는 또 다른 자료구조를 만드는데에도 쓸모가 있다. (ex. 기하학, 연관 배열)

 

01. Red-Black 트리를 C언어로 구현해보자

(1) Red-Black Tree, 노드 구현 

   1) Red-Black Tree를 코드로 구현한다고 했을 때, Red-Black Tree의 노드가 필요한 변수?

      👉 트리를 구성하는 노드와 해당 노드의 색깔

      👉 노드가 가지고 있는 값

      👉 내 왼쪽 노드의 주소값 

      👉 내 오른쪽 노드의 주소값

      👉 내 부모의 주소값

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;

 

 

   2) Red-Black Tree를 코드로 구현한다고 했을 때, Red-Black Tree 는 어떻게 구현할까?

      👉 tree의 루트 노드를 표현할 변수가 필요하다.

      👉 tree의 리프 노드를 표현할 변수가 필요하다.

      👉 여기서 드는 의문은 루트 노드와 리프노드를 코드로 어떻게 표현할까?

      : 포인터(메모리에 저장된 주소값을 반환)로 루트노드와 리프의 주소값을 저장하여 구현한다.

      👉 리프노드의 경우 많은 주소값이 저장될 텐데 효율적으로 사용할 수 있는 방법이 없을까?

      : 리프노드를 효율적으로 구현하기 위해 Sentinel(경계원소)라는 개념을 사용한다. Sentinel(경계원소)는 한계조건을 간단하게 해주는 더미(dummy)객체이다. 각 노드가 nill노드를 바라보게되면 그것은 마지막 리프노드라는 것을 알 수 있고, 이 방법은 각 리프노드의 주소값을 하나씩 저장하는 것보다 훨씬 효율적인 방법이다. 또한 root노드도 같은 방식으로 사용할 수 있다.

typedef struct {
  node_t *root;
  node_t *nil;  // for sentinel
} rbtree;

nill노드를 선언하여 모든 leaf노드와 root노드가 nill노드를 참조하도록 한다.

 

(2) Red-Black Tree, New_rbtree()

    👉 RB tree 구조체 생성 : 함수 new_rbtree는 calloc을 통해 만들 rbtree 메모리를 할당하고 초기화 해준다. 그리고 만든 트리 P의 루트와 nill 의 주소를 초기화 해주면서 여러 개의 tree를 생성해 각각 다른 내용들을 저장할 수 있는 함수이다.

rbtree *new_rbtree(void) {   // TODO: initialize struct if needed
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  node_t *nil_node = (node_t*)calloc(1, sizeof(node_t));
  
  nil_node->color = RBTREE_BLACK;
  
  p -> root = nil_node;
  p -> nil = nil_node;
  return p;
}

 

 

(2) Red-Black Tree, insert()

    👉 RB tree insert : Key 값을 추가하여 RB트리에 노드를 추가하는 함수이다.

    

 

 

 

 

(3) Red-Black Tree, delete()

    👉 RBtree 구조체가 차지했던 메모리 반환 : 해당 tree가 사용했던 메모리를 전부 반환하는 함수이다. 

 

(4) Red-Black Tree, find(tree, key)

    👉 RBtree 의 키값 탐색 : RB tree내에 해당 key가 있는지 탐색하여 있으면 해당 node pointer 반환 함수

 

(5) Red-Black Tree, tree_to_array(tree, array, n)

 

 

 

 

 

02. 참고자료 

Introduction to Algorithms  - 

https://www.youtube.com/watch?v=FPc36I2vzjQ&t=2s&ab_channel=%EC%BD%94%EB%93%9C%EB%9D%BC%EB%96%BC

https://www.youtube.com/watch?v=qA02XWRTBdw&t=877s&ab_channel=Jenny%27slecturesCS%2FITNET%26JRF

https://www.youtube.com/watch?v=SHdYv41iCmE&ab_channel=Chan-SuShin 

 

 

 

 

짱구의 레드블랙트리는 블랙노드가 많다.