크래프톤 정글 WIL_Week05 Red-Black Tree

pigpgw·2024년 8월 18일

크래프톤 정글 6기

개요

5주차 과제는 Red-Black Tree 구현이였다.

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

레드블랙 트리는 자가 균형 이진 탐색 트리의 일종이다. 일반적인 이진 탐색 트리(BST)의 최악의 경우 시간 복잡도인 O(N)을 개선하여 항상 O(logN)의 시간 복잡도를 유지한다.

속성

각 노드는 빨간색(Red) 또는 검은색(Black) 중 하나의 색을 가진다.
루트 노드는 항상 검은색이다.
모든 NIL 노드(리프 노드)는 검은색이다.
빨간색 노드의 자식은 모두 검은색이다. (빨간색 노드는 연속될 수 없음)
어떤 노드에서든 그 노드로부터 자손 NIL 노드들로 가는 모든 경로에는 동일한 개수의 검은색 노드가 있다. (자기 자신은 제외)

NIL 노드

존재하지 않음을 의미하는 노드로, 자녀가 없을 때 자녀를 NIL 노드로 표기한다.
다른 노드와 동등하게 취급된다.
레드블랙 트리에서 모든 리프 노드는 NIL 노드이다.

삽입 연산

일반적인 BST와 동일하게 노드를 삽입한다.
삽입되는 노드의 색은 빨간색이다.
삽입 후 레드블랙 트리의 속성을 위반하는 경우, 다음 세 가지 케이스에 따라 재조정한다.

Case 1: 삽입된 노드의 부모와 삼촌이 모두 빨간색일 때

부모와 삼촌을 검은색으로 변경
할아버지 노드를 빨간색으로 변경
할아버지 노드에서 속성 위반 검사를 다시 수행

Case 2: 삽입된 노드의 부모는 빨간색, 삼촌은 검은색이고, 노드가 "안쪽 손자"일 때

부모를 기준으로 회전 (노드가 왼쪽 자식이면 오른쪽으로, 오른쪽 자식이면 왼쪽으로)
Case 3으로 전환

Case 3: 삽입된 노드의 부모는 빨간색, 삼촌은 검은색이고, 노드가 "바깥쪽 손자"일 때

부모와 할아버지의 색을 교환
할아버지를 기준으로 회전 (노드가 왼쪽 경로에 있으면 오른쪽으로, 오른쪽 경로에 있으면 왼쪽으로)

삭제 연산

삭제 연산은 일반적인 BST의 삭제 연산을 수행한 후, 레드블랙 트리의 속성을 유지하기 위해 재조정 과정을 거친다.

일반적인 BST 삭제 연산을 수행한다.
삭제된 노드가 빨간색이었다면 추가 작업 없이 종료한다.
삭제된 노드가 검은색이었다면, 해당 위치에 "이중 검은색" 노드가 있다고 가정하고 다음 케이스들을 적용하여 재조정한다.

Case 1: 이중 검은색 노드의 형제가 빨간색일 때

형제 노드를 검은색으로, 부모 노드를 빨간색으로 변경
부모를 기준으로 회전 (이중 검은색 노드 방향으로)
다른 케이스로 전환

Case 2: 이중 검은색 노드의 형제가 검은색이고, 형제의 양쪽 자식이 모두 검은색일 때

형제 노드를 빨간색으로 변경
부모 노드를 새로운 이중 검은색 노드로 설정하고 재조정 과정 반복

Case 3: 이중 검은색 노드의 형제가 검은색이고, 형제의 안쪽 자식만 빨간색일 때

형제의 안쪽 자식을 검은색으로, 형제를 빨간색으로 변경
형제를 기준으로 회전 (바깥쪽 방향으로)
Case 4로 전환

Case 4: 이중 검은색 노드의 형제가 검은색이고, 형제의 바깥쪽 자식이 빨간색일 때

형제 노드의 색을 부모 노드의 색으로 변경
부모 노드를 검은색으로 변경
형제의 바깥쪽 자식을 검은색으로 변경
부모를 기준으로 회전 (이중 검은색 노드 방향으로)
이중 검은색을 제거하고 재조정 종료

삭제 연산은 일반적인 이진 탐색 트리의 삭제 방법을 따르되, 레드블랙 트리의 특성을 유지하기 위한 추가적인 재조정 과정이 필요하다. 이 과정은 여러 가지 케이스가 존재하며 다시 말하지만 일반적인 이진 탐색 트리의 삭제 방법을 따르기에 이진 탐색의 삭제 방법을 먼저 시도하고 그다음 재조정을 진행한다고 이애하는게 중요하다.

Red-Black Tree 구현

Balanced search tree로 많이 쓰이는 Red-black tree (이하 RB tree)를 C 언어로 구현하는 과제
구현하는 추상 자료형 (ADT: abstract data type)은 ordered set, multiset 이다.

구현 범위

다음 기능들을 수행할 수 있도록 RB tree를 구현해야한다.

- tree = `new_tree()`: RB tree 구조체 생성
  - 여러 개의 tree를 생성할 수 있어야 하며 각각 다른 내용들을 저장할 수 있어야 합니다.
- `delete_tree(tree)`: RB tree 구조체가 차지했던 메모리 반환
  - 해당 tree가 사용했던 메모리를 전부 반환해야 합니다. (valgrind로 나타나지 않아야 함)

- `tree_insert(tree, key)`: key 추가
  - 구현하는 ADT가 multiset이므로 이미 같은 key의 값이 존재해도 하나 더 추가 합니다.
- ptr = `tree_find(tree, key)`
  - RB tree내에 해당 key가 있는지 탐색하여 있으면 해당 node pointer 반환
  - 해당하는 node가 없으면 NULL 반환
- `tree_erase(tree, ptr)`: RB tree 내부의 ptr로 지정된 node를 삭제하고 메모리 반환
- ptr = `tree_min(tree)`: RB tree 중 최소 값을 가진 node pointer 반환
- ptr = `tree_max(tree)`: 최대값을 가진 node pointer 반환

- `tree_to_array(tree, array, n)`
  - RB tree의 내용을 *key 순서대로* 주어진 array로 변환
  - array의 크기는 n으로 주어지며 tree의 크기가 n 보다 큰 경우에는 순서대로 n개 까지만 변환
  - array의 메모리 공간은 이 함수를 부르는 쪽에서 준비하고 그 크기를 n으로 알려줍니다.

구현 규칙

src/rbtree.c 이외에는 수정하지 않고 test를 통과해야 한다.
make test를 수행하여 Passed All tests!라는 메시지가 나오면 모든 test를 통과한 것이다.
Sentinel node를 사용하여 구현했다면 test/Makefile에서 CFLAGS 변수에 -DSENTINEL이 추가되도록 comment를 제거해 준다.

과제의 의도 (Motivation)

복잡한 자료구조(data structure)를 구현해 봄으로써 자신감 상승
C 언어, 특히 포인터(pointer)와 malloc, free 등의 system call에 익숙해짐.
동적 메모리 할당(dynamic memory allocation)을 직접 사용해 봄으로써 동적 메모리 할당의 필요성 체감 및 data segment에 대한 이해도 상승
고급 언어에서 기본으로 제공되는 자료구조가 세부적으로는 어떻게 구현되어 있는지 경험함으로써 고급 언어 사용시에도 효율성 고려

RB Tree 미션은 위에서 말했듯이 BST를 이해하고 그다음 RB Tree의 특성과 ,RB Tree의 삭제가 동작하는지를 이해하는게 중요하다.

레드-블랙 트리 구현 과정

1. 기초부터 시작하기: BST 복습

레드-블랙 트리(RB Tree)는 자가 균형 이진 탐색 트리의 일종으로, 복잡한 자료구조이다. 이 과제에 접근하면서 나는 "기본기가 없다면 어차피 돌아온다"는 생각에 이전에 학습했던 이진 탐색 트리(BST) 구현을 복습했다.

BST의 기본 연산(삽입, 삭제, 검색)을 재검토
트리 순회 방법(전위, 중위, 후위)을 다시 구현

2. RB Tree 이론 학습

BST를 충분히 복습한 후, RB Tree의 특성과 규칙을 공부했다.

모든 노드는 빨간색 또는 검은색
루트 노드는 항상 검은색
모든 리프 노드(NIL)는 검은색
빨간색 노드의 자식은 반드시 검은색 (빨간색 노드가 연속으로 나올 수 없음)
모든 리프 노드에서 Black Depth는 같아야 함

삽입과 삭제 연산 시 이러한 규칙을 유지하기 위한 재조정 과정(회전, 색상 변경)을 이해하는 데 집중했다.

3. 시각화를 통한 이해

RB Tree의 다양한 케이스를 이해하기 위해 직접 그림을 그리며 공부했다.

삽입 시 발생할 수 있는 케이스들 (삼촌 노드의 색상에 따른 처리)
삭제 시 발생할 수 있는 케이스들 (대체 노드와 형제 노드의 색상에 따른 처리)

4. 구현 단계

4.1 단일 NIL 노드 사용

단일 NIL 노드를 사용하여 메모리 사용을 최적화하고 구현을 단순화하고자 root 노드와 모든 리프 노드에 붙는 nill 노드를 처리했다.

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  node_t * nil = (node_t*)calloc(1,sizeof(node_t));

  nil->color = RBTREE_BLACK;
  nil->key = NULL;

  p->nil = nil;
  p->root = nil;
  return p;
}

4.2 삽입 구현

삽입 연산은 일반적인 BST 삽입 후 RB Tree 속성을 유지하기 위한 재조정 과정을 고려하는 방식으로 진행했다.

node_t *rbtree_insert(rbtree *t, const key_t key) {
  // 새 노드 생성 및 BST 삽입 로직
  // ...

  z->color = RBTREE_RED;
  rb_insert_fixup(t,z);
  
  return z;
}

rb_insert_fixup 함수에서 삽입 후 속성 유지를 위한 로직을 구현했고

4.3 삭제 구현

삭제 연산은 노드를 삭제한 후 트리의 균형과 색상 속성을 유지하게 만들었다.

int rbtree_erase(rbtree *t, node_t *z) {
  // 삭제 대상 노드 찾기 및 삭제 로직
  // ...

  if(y_original_color == RBTREE_BLACK)
    rb_delete_fixup(t,x);
  free(z);
  return 0;
}

마무리

아쉽게도 RB tree의 내용을 key 순서대로 주어진 array로 변환하는 마지막 문제는 시간 부족으로 해결하지 못서 아쉬웠지만 깨달은게 많은 주차였다. 테스트 케이스 파악, c언어의 숙련도, 로직 설계등 깨달은게 많지만 현재도 시간이 부족하기에 해당 내용들은 블로그에 모두 적지는 않고 정글을 진행하면서 꾸준히 개선하기로하고 이번주 WIL을 마무리 하고자 한다.

pigpgw

https://www.pigpgw.cloud 로 이전합니다~

이전 포스트

크래프톤 정글 WIL_Week04

다음 포스트

크래프톤 정글 WIL_Week05 Red-Black Tree