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

https://github.com/Yoosun-Chang/rbtree-lab

• 전체 코드

구현 범위

다음 기능들을 수행할 수 있도록 RB tree를 구현합니다.

• tree = new_tree(): RB tree 구조체 생성

  • 여러 개의 tree를 생성할 수 있어야 하며 각각 다른 내용들을 저장할 수 있어야 합니다.

  RB tree 구조체 생성

• delete_tree(tree): RB tree 구조체가 차지했던 메모리 반환

  • 해당 tree가 사용했던 메모리를 전부 반환해야 합니다. (valgrind로 나타나지 않아야 함)

  Tree 삭제

• tree_insert(tree, key): key 추가

  • 구현하는 ADT가 multiset이므로 이미 같은 key의 값이 존재해도 하나 더 추가 합니다.

  key 추가

• ptr = tree_find(tree, key)

  • RB tree내에 해당 key가 있는지 탐색하여 있으면 해당 node pointer 반환
  • 해당하는 node가 없으면 NULL 반환

  탐색

• tree_erase(tree, ptr): RB tree 내부의 ptr로 지정된 node를 삭제하고 메모리 반환

  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으로 알려줍니다.

  array로 변환

구현 규칙

• src/rbtree.c 이외에는 수정하지 않고 test를 통과해야 합니다.
• make test를 수행하여 Passed All tests!라는 메시지가 나오면 모든 test를 통과한 것입니다.