---

[WEEK04] 탐험준비 - Red-Black Tree

📢 “정글끝까지 가기 전에, 준비운동을 하며 필수 스킬을 익혀봅시다!”

지난 3주간은 고급 언어인 Python 언어로 가변 리스트, 우선순위 큐와 같은 추상화된 데이터 타입 (abstract data type)을 사용하여 컴퓨터를 다루는 방법을 익혔습니다. 이번 3주간은 Assembly 언어와 매우 가까운 C언어를 사용하여 좀 더 컴퓨터의 본질에 가까이 가 봅시다. 3주간 각 1주차 씩 Red-Black tree → malloc → 웹 proxy 서버를 C언어로 구현하면서, C언어 포인터의 개념, gdb 디버거 사용법 등을 익혀봅니다. 또한, Segmentation fault 등 새로운 에러들을 마주해봅니다! 🙂 알고리즘(CLRS), 컴퓨터 시스템(CS:APP) 교재를 참고하여 진행합니다. RB tree - CLRS 13장, malloc - CS:APP 9장, 웹서버 - CS:APP 11장

---

💡 Ubuntu 22.04 LTS (x86_64)환경을 사용합니다.

개발 환경 설치

sudo apt update                         # package list update
sudo apt upgrade                        # upgrade packages
sudo apt install gcc make valgrind gdb  # gcc, make 등 개발 환경 설치

GitHub 토큰 관리를 위한 gh 설치

curl -fsSL https://cli.github.com/packages/githubcli-archive-keyring.gpg | sudo dd of=/usr/share/keyrings/githubcli-archive-keyring.gpg
sudo chmod go+r /usr/share/keyrings/githubcli-archive-keyring.gpg
echo "deb [arch=$(dpkg --print-architecture) signed-by=/usr/share/keyrings/githubcli-archive-keyring.gpg] https://cli.github.com/packages stable main" | sudo tee /etc/apt/sources.list.d/github-cli.list > /dev/null
sudo apt update
sudo apt install gh

(컨테이너에 GitHub Cli를 추가적으로 설치해놓기는 함)

---

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에 대한 이해도 상승
• 고급 언어에서 기본으로 제공되는 자료구조가 세부적으로는 어떻게 구현되어 있는지 경험함으로써 고급 언어 사용시에도 효율성 고려

참고문헌

• 위키백과: 레드-블랙 트리 (영어)
• CLRS book (Introduction to Algorithms) 13장 레드 블랙 트리 - Sentinel node를 사용한 구현
• Wikipedia:균형 이진 트리의 구현 방법들