2025.04.19

TIL(TODAY I LEARN)

---

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

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

• 삽입까지 완료! 화이팅

---

(1) new_rbtree()

 if (p == NULL) return NULL; // 할당 실패시 널 반환(메모리 부족 상태)
  
  node_t *n = malloc(sizeof(node_t));
  if (n == NULL) {
    free(p); // 닐 노드 실패했으니 rbtree 구조체도 반환해야함!
    return NULL;
  }

• 항상 할당 실패를 했을 때를 고려하자!

typedef struct node_t {
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;

typedef struct {
  node_t *root;
  node_t *nil;  // for sentinel
} rbtree;

• rbtree 구조체는 nil 포인터만 갖고 있기 때문에 rbtree를 새로 구성할때 node_t에 malloc 필요!
  • node_t 할당 실패 시에 안된거니까 free(p) 필요!

(2) delete_rbtree()

• 모든 트리를 삭제하기 위해서는 모든 노드에 대해서 할당해제가 필요함
• 후위 순회를 진행하면서 모든 노드에 대해서 해제 필요

static void del_node(rbtree *t, node_t* n){ //파일 내부에서만 돌아가는 헬퍼함수
  if (n == t->nil){ //끝(nil)이면 그냥 리턴
    return ;
  }
  del_node(t, n->left);
  del_node(t, n->right);
  free(n);
}

• 현재 함수는 rbtree* 를 인자로 받고 있기 때문에 노드를 해제 해 줄 헬퍼함수가 작성
  • static? 헬퍼함수?
    • 함수에 붙인 static
      • 내부 연결성 부여 → 현재 소스파일 내부에서만 보임
    • 변수에 붙인 static
      • 함수 바깥(global)에서 선언
        • 파일 범위의 정적 변수 → 외부(.o)로 노출되지 않는 전역 변수
      • 함수 안(local)에서 선언
        • 블록이 끝나도 사라지지 않는 영속적 저장공간
        • 호출 간에 값이 유지됨
    • 헬퍼함수
      • 주 함수의 동작을 분할, 단순화 하기 위해 만든 보조함수
      • 가독성, 재사용성, 유지보수성 ↑

(3) rbtree_insert()

• BST 처럼 위치를 먼저 찾는다.
• 부모 자식 연결 ( 빈 트리일 경우 생각)
• 삽입된 노드는 리프 노드임, 무조건 빨간색!
• RB_Insert_Fixuip() 함수를 통해 색 보정을 한다.
  • RB_Insert_Fixuip()
  • case 1,2,3 검사해서 진행
  • case 2,3 일 경우 Rotate() 함수를 통해 회전.

(4) rbtree_find()

• 검색은 BST와 동일
• 루트부터 같으면 리턴
• 작으면 left 크면 right