자료구조, RBtree 구현

728x90

자료구조, RBtree 구현

2023.04.04 - [알고리즘] - 자료구조, AVL

📌 RBtree란?

RBtree 출처 :&nbsp;CLRS book (Introduction to Algorithms)

AVL 자가균형트리의 한 종류로, 가장 많이 사용되는 균형 이진탐색트리이다.
다음과 같은 속성을 지닌다.

1. 모든노드는 red 혹은 black
2. 루트 노드는 black
3. 모든 nil(leaf)노드는 black
4. red의 자녀들은 black(red가 연속적으로 존재할 수 없다)
5. 임의의 노드에서 자손 nil노드들까지 가는 black 수는 같다(자기자신제외)

자가균형트리 AVL에서는 양쪽 부트리 높이가 중요하다.
그러므로 5번 속성이 굉장히 중요하다.

📌 이러한 자료 구조가 필요한 이유?

중간값 자료가 필요할 때!
다른 말로, 최솟값 & 최댓값이 필요한 경우(sort)가 아닐때.
데이터 삽입/삭제가 계속 일어날 때 → Linked List 사용 이유와 동일

📌 Sentinal이란?

실제 노드는 아니지만 노드와 같은 구조를 가지는 특수한 노드(더미 노드)
일반적으로 NIL이나 NULL 값을 가지며, 트리의 빈 공간을 나타내는 역할 합니다.

📄 Makefile

-DSENTINEL

rbtree 구현시, 테스트 케이스에 다음과 같은 구문이 있으면, Sentinal을 nil값으로 설정해 코드를 구현 할 수 있습니다.
만약, '나는 Sentinal을 NULL값을 가지는 rbtree를 구현하고 싶다.' 하시는 분들은 컴파일 옵션을 주석처리해 주면 됩니다.

📌 RBtree 생성

📄 rbtree.c

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

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

rbtree *new_rbtree(void) {
  rbtree *t = (rbtree *)calloc(1, sizeof(rbtree));
  node_t *NIL = (node_t *)calloc(1, sizeof(node_t));
  NIL->color = RBTREE_BLACK; // NIL 노드 색깔은 항상 블랙.
  // rbtree sentinal 설정
  t->nil = NIL;
  t->root = NIL;
  return t;
}

📄 test-rbtree.c

void test_init(void) {
  rbtree *t = new_rbtree();
  assert(t != NULL);
#ifdef SENTINEL
  assert(t->nil != NULL);
  assert(t->root == t->nil);
#else
  assert(t->root == NULL);
#endif
  delete_rbtree(t);
}

위와 같은 구문을 사용하여 SENTINEL이 정의되어 있을 때만 코드를 컴파일할 수 있습니다.

📌 Sentinel을 사용하는 이유는?

Red-Black 트리에서 노드의 자식노드가 NIL인 경우, 이를 블랙 노드로 취급하기 위해서 사용합니다.
자식이 없는 노드를 구분할 수 있습니다.
rbtree에서는 루트노드와 리프 노드의 자식 노드들을 NIL값을 가지는 노드(sentinel)로 처리해 트리의 경계를 명확하게 나타낼 수 있습니다. 트리의 경계를 명확하게 하는 이유는 트리의 구조를 보존하기 위해서 입니다.
트리의 노드들이 일정한 높이를 유지할 수 있습니다. sentinel을 사용하지 않으면, 루트 노드나 NIL값을 가진 노드의 높이가 달라지는 문제가 발생할 수 있습니다.

rbtree의 경계를 명확하게 함으로써 트리의 규칙을 잘 지킬 수 있습니다.
즉, 탐색, 삽입, 삭제 등의 연산 과정에서 예상치 못한 결과를 방지하기 위해서 사용합니다.

cf. Linked List의 head를 사용하는 이유와 유사.

📌 더 생각해 볼 내용

📄 Node 구조체

typedef struct node_t {
  int color;
  struct node_t *parent;
  struct node_t *child[2];
} node_t;

왼쪽 자식을 child[0], 오른쪽 자식을 child[1]로 설정. 배열값을 이용해 0,1로 표현할 수 있음!
만약 왼쪽 자식에 접근하기 위해서는 (현재 자식노드-1)을 해주면 된다.

또한 노드의 color 메모리를 줄이기 위해 다음과 같이 선언해 줄 수 있다.

typedef enum {
    RBTREE_BLACK = 0,
    RBTREE_RED = 1
} color;

typedef struct node_t {
    color c : 1; // 1 bit를 사용하여 color 필드 저장
    key_t key;
    struct node_t *left;
    struct node_t *right;
    struct node_t *parent;
} node_t;

📄 동적메모리 해제 후, Null처리

free(p);
p = NULL;

방어 프로그래밍의 한 형태로, 메모리 블록을 해제 후 다시 사용할 수 있는 버그나 오류를 방지해준다.

성능과 안전성을 높이기 위해 메모리 해제 후 NULL을 할당해주는 것이 좋다.

꼭 필요한 코드는 아니지만, 호출 후 포인터 변수를 할당하는 것은 좋은 습관이라고 할 수 있다.

공부 자료 : CLRS book (Introduction to Algorithms) 13장 레드 블랙 트리

저작자표시

'알고리즘' 카테고리의 다른 글

백준 10971, 외판원 순회 2 (0)	2023.05.21
DFS 순열, 조합 (0)	2023.05.21
자료구조, rbtree delete (0)	2023.04.06
자료구조, rbtree insert (0)	2023.04.06
자료구조, AVL Left-Rotate & Right-Rotate 구현 (0)	2023.04.04

팽이의 개발일기

자료구조, RBtree 구현