[정글] Week05 - Data Structure #2

Week05 기간 2024.10.11 FRI - 2024.10.17 THU 
조원 ㅅㅎ ㅈㅎ

 

Data Structure 구현 Red-Black Tree

RBTREE 기본 개념 https://helloahram.tistory.com/89

RBTREE 함수 구현 #1 https://helloahram.tistory.com/92

RBTREE 함수 구현 #2 https://helloahram.tistory.com/101

No.	To-do-List	구현 여부
1	Gitgub Repository 생성	O
2	new_rbtree	O
3	delete_rbtree
4	rbtree_insert	O
5	rbtree_find	O
6	rbtree_min	O
7	rbtree_max	O
8	rbtree_erase
9	rbtree_to_array

테스트 케이스

No.	Test Case Check	진행 여부
1	test_init
2	test_insert_single
3	test_find_single
4	test_erase_root
5	test_find_erase_fixed
6	test_minmax_suite
7	test_to_array_suite
8	test_distinct_values
9	test_duplicate_values
10	test_multi_instance
11	test_find_erase_rand

공부 키워드

No.	Keyword	정리 내용
1	포인터	https://helloahram.tistory.com/72
2	가상화	https://helloahram.tistory.com/90
3	GCC (GNU Complier Collector)	https://helloahram.tistory.com/73
4	포인터의 연산
5	동적 메모리 할당	https://helloahram.tistory.com/85
6	이진 탐색 트리	https://helloahram.tistory.com/97
7	레드 블랙 트리의 삽입/ 삭제	https://helloahram.tistory.com/89
8	malloc, calloc, realloc

책 읽기 

No.	Keyword	정리 내용
1	3장 프로그램의 기계 수준 표현 특히 3.4, 3.7, 3.8	https://helloahram.tistory.com/66
2	7장 링커 특히 7.1, 7.4, 7.9, 그림 7.15	https://helloahram.tistory.com/95
3	8장 예외적인 제어 흐름 특히 8.1, 8.5
4	9장 가상 메모리 특히 9.9, 9.11

 

 

---

 

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:균형 이진 트리의 구현 방법들