2025.04.20

TIL(TODAY I LEARN)

---

• 오늘한 내용 : 고급 자료 구조 :RED-BLACK-TREE 구현

• WEEK06: 메모리 누수, 균형 이진 탐색 트리(AVL Tree, Red-Black Tree)

• 삭제, 배열로 끝

---

(5) rbtree_min()

• 빈 트리일 때 NULL 반환
• 루트부터 왼쪽으로 계속 반복

(6) rbtree_max()

• 빈 트리일 때 NULL 반환
• 루트부터 오른쪽으로 계속 반복

(7) rbtree_erase()

• BST 삭제와 같음
• 일단 BST 성질을 따라 삭제를 진행
  • RB_Transplant() 사용
  • succesor 구할 때 서브트리의 최솟값을 찾기 위한 함수 subtree_min() 함수 사용
    
• 삭제한 노드가 블랙이라면? → case 1,2,3,4 따라 색 보정 진행
  • RB_Delete_Fixup()
  • x가 왼쪽 자식이냐, 오른쪽 자식이냐에 따라 반대(mirror)

(8) rbtree_to_array()

• 중위 순회(오름차순) 하면서 arr의 크기만큼만 넣어줌.
• c에서는 append() 가 없기 때문에 idx를 넘겨주어 하나씩 증가해야함
• insert_arr()함수 기저 조건에는 x가 nil 인지, idx가 n을 넘지 않는지 검사

static size_t insert_arr(const rbtree *t, node_t* x, key_t *arr, size_t idx, const size_t n){
  if (x == t->nil || idx >= n){ //n 넘으면 바로 리턴
    return idx;
  }
  //중위 순회
  idx = insert_arr(t,x->left, arr, idx, n);
  arr[idx] = x->key;
  idx ++;
  return insert_arr(t,x->right, arr, idx, n);
}

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
//idx 0부터 시작
	size_t filled = insert_arr(t, x, arr, 0, n);
}

• const?
  • C 언어에서 const는 “변경 불가능”이라는 뜻의 타입 한정자(type qualifier)
    • 포인터가 가리키는 대상을 수정하지 않겠다는 약속을 컴파일러에 알림.
    • 잘못 건드리면 컴파일 오류가 나서, 실수로 데이터가 바뀌는 걸 막아줌.