[TIL] Red-Black Tree 구현하기 #1

Red-Black Tree 기본 개념 을 숙지했으니 이제 구현을 해봤다 

rbtree.h 분석

1. enum color_t

// RBTREE 색을 열거형으로 정의하고, color_t 라는 이름으로 새로운 자료형 정의
// Red, Black 를 각각 RBTREE_xxx 으로 정의하여 color_t nodeColor; 로 사용 가능
// ex) nodeColor = RBTREE_RED; or nodeColor = RBTREE_BLACK;
typedef enum
{
  RBTREE_RED,
  RBTREE_BLACK
} color_t;

2. int key_t

// RBTREE 의 키 값을 나타내는 정수형 변수를 key_t 라는 이름으로 정의
typedef int key_t;

3. struct node_t

struct rbtree 와 달리 struct node_t 를 선언할 때 [node_t] 를 써주는 이유는 

1. 구조체가 완전히 정의되기 전에 구조체 정의의 일부로 자기 자신의 포인터 변수를 사용하기 때문

2. 이름을 미리 선언한 후, 그 이름을 구조체 내부에서 포인터로 사용 가능 

// RBTREE 의 노드를 나타내는 구조체 정의
typedef struct node_t
{
  color_t color;                        // 노드의 색상 RED or BLACK
  key_t key;                            // 노드가 저장하는 키 값
  struct node_t *parent, *left, *right; // 부모, 왼쪽 자식, 오른쪽 자식을 나타내는 포인터
} node_t;

4. struct rbtree

// RBTREE 자체를 나타내는 구조체 정의
typedef struct
{
  node_t *root; // 트리의 루트 노드를 가리키는 포인터
  node_t *nil;  // nil 노드를 가리키는 포인터, Sentinel 로 사용
} rbtree;

 

그 외 나머지 함수는 내가 구현할 것들!

 

rbtree.c 구현 #1

1. rbtree 초기화 함수 rbtree *new_rbtree(void)

트리를 만드는 rebtree 포인터 변수 p 와 트리의 구성 요소 p->nil 을 선언하고 메모리를 할당한다

nil 노드를 만들어 주는 이유는 RBTree 에서는 트리가 비어 있는 상태에서도 root 가 nil 을 가리키고 있어야 하고 

삽입/ 삭제/ 탐색 등의 연산에서 트리의 끝을 만날 때마다 항상 nil 노드를 사용하기 때문이다 

트리의 모든 리프 노드가 트리의 상태에 관계 없이 동일한 nil 노드를 참조하게 되어 메모리 낭비를 줄일 수 있다 

 rbtree *new_rbtree(void)
{
  // rebtree 구조체에 대한 메모리 할당
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  if (NULL == p) // p 메모리 할당에 실패할 경우
    return NULL;

  // nil Node 구조체에 대한 메모리 할당
  p->nil = (node_t *)calloc(1, sizeof(node_t));
  if (NULL == p->nil) // p->nil 메모리 할당에 실패할 경우
  {
    free(p); // p 메모리 할당 해제
    return NULL;
  }

  // calloc 이 메모리 할당 + 초기화 이기 때문에 색만 지정
  p->nil->color = RBTREE_BLACK;

  // 트리의 Root Node 와 nil Node 초기화
  p->root = p->nil; // 초기 Root 는 nil 로 설정

  // 생성한 트리 반환
  return p;
}

 

2. 최소값 찾기 node_t *rbtree_min(const rbtree *t)

RB Tree 특성 상 루트보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치하기 때문에 

가장 작은 값은 가장 왼쪽 끝에 있는, 자식이 없는 노드가 가지고 있다 

node_t *rbtree_min(const rbtree *t)
{
  // TODO: implement find
  // nil node 를 제외하고 가장 왼쪽 자식에 있는 자식 노드가
  // 트리에서 가장 작은 값이기 때문에 끝까지 탐색

  // root node 부터 탐색 시작
  node_t *current = t->root;

  // current->left 가 nil node 인 경우 가장 작은 값이므로
  // current->left 가 nil node 일 때까지 탐색
  while (current->left != t->nil)
  {
    current = current->left;
  }

  return current;
}

 

3. 최대값 찾기 node_t *rbtree_max(const rbtree *t)

가장 큰 값도 가장 오른쪽 끝에 있는, 자식이 없는 노드가 가지고 있다 

node_t *rbtree_max(const rbtree *t)
{
  // TODO: implement find
  // nil node 를 제외하고 가장 오른쪽 자식에 있는 자식 노드가
  // 트리에서 가장 큰 값이기 때문에 끝까지 탐색

  // root node 부터 탐색 시작
  node_t *current = t->root;

  // current->left 가 nil node 인 경우 가장 작은 값이므로
  // current->left 가 nil node 일 때까지 탐색
  while (current->right != t->nil)
  {
    current = current->right;
  }

  return current;
}

 

4. 특정 값 찾기 node_t *rbtree_find(const rbtree *t, const key_t key)

node_t 포인터 변수를 root 노드에 위치시키고, 찾으려는 값 key 과 비교한다 

현재 값보다 찾는 값이 크면 왼쪽 서브트리로 이동, 찾는 값이 작으면 오른쪽 서브트리로 이동하면서 

찾고자 하는 값에 도달하면 해당 노드를 반환하고, 만약에 찾는 값이 트리에 없다면 NULL 을 반환한다 

node_t *rbtree_find(const rbtree *t, const key_t key)
{
  // TODO: implement find
  // root node 부터 탐색 시작
  node_t *current = t->root;

  // nil->node 도달까지 (Key 를 못 찾을 때까지) 탐색 진행
  // 찾는 값 key 과 현재 값 current->key 를 비교
  // Current 와 비교했을 때 Key 가 작다면 왼쪽으로 이동
  // Current 와 비교했을 때 Key 가 크다면 오른쪽으로 이동
  while (current->key != t->nil)
  {
    // 현재 값보다 찾는 값이 클 때 왼쪽으로 이동
    if (current->key > key)
      current = current->left;
    // 현재 값보다 찾는 값이 작을 때 오른쪽으로 이동
    else if (current->key < key)
      current = current->right;
    // Key 를 찾았을 때 해당 노드 current 반환
    else
      return current;
  }

  // nil node 까지 도달했지만 Key 가 없는 경우,
  // node_t * 반환 타입에 맞게 NULL return
  return NULL;
}