2025.04.14

TIL(TODAY I LEARN)

---

• 오늘한 내용 : C - BST, B-tree, Allocation

• WEEK05: C Pointer(&, * 연산자), 동적 메모리 할당, Linked List, Stack, Queue, Binary Tree, Binary Search Tree, 동적 프로그래밍, 그리디 알고리즘

• 계속해서 C언어를 공부해보자!!

---

• 어제 덜한 4, 5번

4. Binary Search Tree

(4) postOrderIterativeS1()

1. 왼쪽 자식 끝까지 push
2. 오른쪽 자식 있으면 push
3. 둘 다 없거나 방문 완료 → 출력
4. 마지막 출력한 노드 기억(lastvisited) → 오른쪽 자식 재방문 방지

dwn_chk == 1	트리 내려가면서 자식 push하는 구간
up_chk == 1	올라오면서 부모 처리(출력) 여부 확인
lastvisited	오른쪽 자식이 이미 처리되었는지 판별

(5) postOrderIterativeS2()

• 스택 2개 쓰니까 자식노드 좌, 우 구분 잘하기

---

내가 정리하는 B-tree

B-Tree의 사용 목적

1. 높이 최소화 (디스크 접근 최소화)
2. 균형 유지 (모든 리프 노드가 같은 깊이)
3. 삽입/삭제 시에도 항상 조건을 만족하도록 보장

→ 디스크 접근을 최소화 해서 성능을 높이자!

높이가 낮아지면 왜 디스크 접근이 최소화 되는건데?

디스크 접근을 최소화 하면 성능이 왜 올라가는데?

• 디스크는 메모리보다 엄청 느리다(메모리 나노초 / 디스크 밀리초)
• 트리 탐색 : 루트 → 리프 방향 == 트리의 높이 == 거치는 노드 수
• B 트리의 한 노드 = 디스크 블록 1개 → 높이가 작을수록 디스크 블록을 덜 읽어도 된다!

→ 근데 높이가 낮아지는 만큼 너비가 넓어지면 또이또이 아닌가?

• 아니다! 디스크는 블록단위로 읽는다!
  • 그냥 하나 읽을래도 블록 통째로 가져옴
  • 블록 안에는 수십~ 수백개의 키 저장되어있음
  • 오히려 효율 좋다 - 어짜피 블록 단위로 읽는거 그냥 한번에 가져오는 것

---

B 트리의 특징

• 최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리
• 노드는 최대 M개의 자식 노드를 가질 수 있다. ex) 3차 B-트리라면 최대 3개의 자식 노드를 가질 수 있다.
  
• 노드에는 최대 M-1개의 KEY를 가질 수 있다. ex) 3차 B-트리라면 최대 2개의 KEY를 가질 수 있다.
  
• 각 노드는 최소 ⌈M/2⌉개의 자식 노드를 가진다. (루트 노드와 leaf 노드 제외) ex) 3차 B-트리라면 각 노드는 최소 2개의 자식 노드를 가진다.
  
• 각 노드는 최소 ⌈M/2⌉-1개의 키를 가진다. (루트 노드 제외) ex) 3차 B-트리라면 각 노드는 최소 1개의 키를 가진다.
  
• internal 노드의 KEY가 x개라면 자녀 노드의 수는 언제나 x+1 개다.

---

B 트리 검색

• root 노드 시작, key값 순회 하면서 대소비교
  • k와 같은 key 존재 → 검색 끝
  • 대소 비교 후 그 위치 찾으면 → 자식노드로
• leaf노드 도달까지 위 과정 반복
  • leaf에도 값이 없으면 검색 실패

---

B 트리 삽입

• 삽입하기 적절한 리프노드의 위치 검색
  1. 분할 X 경우 - 리프노드에 key 넣을 자리 존재
     1. 적절위치에 삽입
  2. 분할 O 경우 - 리프노드에 key가 가득참
     1. 리프노드에 삽입 후 중앙값을 부모로 보낸다.
     2. 각 값을 중앙값의 왼쪽, 오른쪽 자식으로 설정
     3. 위 과정 루트까지 반복

---

B 트리 삭제

• 삭제 후 최소 key 수보다 적어졌다면, 재조정
  • 최소 key의 수는 m/2 - 1
    1. 삭제할 key가 리프에 있는 경우
       1. 최소 key 개수보다 크면? → 단순 삭제
       2. 왼쪽 or 오른쪽 형제 노드 key 가 최소 key 개수 이상이면?
          1. 부모의 값으로 key를 대체
          2. 왼쪽 형제노드의 가장 큰 값 or 오른쪽 형제노드의 가장 작은 값을 부모 key로
       3. 형제 모두 최소 key, 부모노드 key가 최소 개수 이상이면?
          1. key 삭제
          2. 부모 key를 내려 형제 노드에 병합
       4. 자신, 형제,부모 모두 최소 key 이하면?
          1. 재구조화 과정 3 의 과정 수행

       ---

    2. 삭제할 key가 내부 노드이고 , 노드나 자식에 key가 최소보다 많을 경우
       1. 자손들 중 가장 큰(작은) 노드와 자리 바꿈
       2. 삭제 수행

       ---

    3. 삭제할 key가 내부노드이고, 노드,자식 key 모두 최소 key 개수인 경우
       1. 재구조화가 일어남
          1. key 삭제
          2. key 자식들을 병합
          3. 원래 key의 부모를 key의 형제 노드에 붙이고
          4. key 자식들을 iii의 경우에 붙여줌
          5. iii의 개수가 최대 key 이상이면 중간값 부모로 노드분할 수행

• B-tree.. 삭제부터는 머리가 너무 아파온다. 어려운 녀석.

---

동적 메모리 할당

• 컴파일 타임이 아닌 런타임(runtime) 중에 필요한 크기만큼 메모리를 할당받는 것
• 주로 배열의 크기가 유동적일 때 사용함
• stdlib.h 헤더 파일에 정의되어 있음

---

1. malloc (Memory Allocation)

void* malloc(size_t size);

• size 바이트만큼 메모리 블록을 할당
• 반환: 할당된 메모리 블록의 시작 주소 (void*)
• 특징: 초기화 안 됨 → 쓰레기 값이 들어있음

int* arr = (int*)malloc(5 * sizeof(int));  // int 5개 공간 할당

---

2.calloc (Contiguous Allocation)

void* calloc(size_t num, size_t size);

• num × size 바이트만큼 연속된 메모리 블록을 할당
• 반환: void* 포인터
• 특징: 0으로 초기화됨

int* arr = (int*)calloc(5, sizeof(int));  // int 5개 공간 할당하고 0으로 초기화

---

3. realloc (Reallocation)

void* realloc(void* ptr, size_t new_size);

• 이미 할당한 메모리(ptr)의 크기를 변경
• 새 크기의 메모리를 확보하고, 기존 데이터 복사
• 반환: 새로 할당된 메모리 주소

int* arr = (int*)malloc(5 * sizeof(int));
arr = (int*)realloc(arr, 10 * sizeof(int));  // 크기 변경

---

주의사항

항목	주의할 점
반환값 확인	NULL이면 메모리 부족. 항상 체크 필요
사용 후 해제	free(ptr)로 반드시 해제해야 메모리 누수 방지
타입 변환	void*를 원하는 타입으로 형변환 필요

할당 함수들의 반환형 void*

• allocation 함수들은 단순히 메모리만 할당
• 개발자가 어떤 데이터 형을 저장하는지 알 수 없음.
• 개발자가 알아서 용도 변경하세요~

포인터 함수로 받는이유?

• 메모리 할당한 곳을 가리키겠다!
• 배열의 첫번째 주소와도 같음

---

realloc 함수의 원리

• realloc 할때는 왜 함수를 받아줘야 할까
  • 함수 안에 arr 써주는데?
• realloc은 기존 메모리 공간을 확장하려 시도함
• 확장이 가능하면: 같은 주소에서 크기만 늘림 → 기존 주소 그대로
• 확장이 불가능하면:
  • 새로운 메모리 공간을 새로 확보하고
  • 기존 데이터를 복사한 후
  • 이전 메모리는 자동으로 free되지 않음 (따로 관리해야 함)
  • 그래서 새로운 주소를 반환 → realloc 시 반환한 주소 값을 받아주어야함!
    

realloc추가 팁: 항상 안전하게 쓰기

int* temp = realloc(arr, new_size);
if (temp != NULL) {
    arr = temp;
} else {
    // realloc 실패 → arr는 그대로 유지됨
    // 메모리 누수 없음
}

→ 이렇게 쓰면 realloc 실패 시에도 arr는 그대로 유지돼서 안전

→ allocation 함수 들은 실패 시 NULL 을 반환하기 때문에 실패에 대비하자