[04.14/week05]TIL

CHO WanGi·2025년 4월 14일

KRAFTON JUNGLE 8th

목록 보기

28/89

오늘 한줄 요약

과거의 나야 왜그랬어...

새롭게 배우게 된 것

C언어 구조체 & 구조체 포인터 (연결리스트)
B Tree 삽입 삭제

C언어 구조체 & 포인터

구조체는 다양한 자료형의 변수들을 모아서 하나의 자료형으로 만들어서 더 편하게 코드를 구현할 수 있도록 도와주는 것.

typedef struct _human
{
	int age;
	char[20] name;
    
} Human;

이런식으로 여러 변수를 한데 묶어서 활용할 수 있다.

int main() {
    // 구조체 변수 선언
    Human person;

    // 구조체 멤버 접근 및 값 할당
    person.age = 25;
    strcpy(person.name, "John");

    // 구조체 멤버 출력
    printf("Name: %s\n", person.name);
    printf("Age: %d\n", person.age);

    return 0;
}

따라서 함수에서 구조체 변수를 선언하고
구조체의 데이터, 즉 멤버에 접근하여 값 할당까지 할 수 있다.

그리고 포인터를 활용해서 구조체 멤버에 접근하고 값을 할당할 수도 있는데,

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _human {
    int age;
    char name[20];
} Human;

int main() {
    // 구조체 포인터 생성 + 동적 메모리 할당
    Human *ptr = (Human *)malloc(sizeof(Human));

    if (ptr == NULL) {
        printf("메모리 할당 실패\n");
        return 1;
    }

    // 구조체 포인터를 이용한 값 할당
    ptr->age = 22;
    strcpy(ptr->name, "Daniel");

    // 출력
    printf("Name: %s\n", ptr->name);
    printf("Age: %d\n", ptr->age);

    // 메모리 해제
    free(ptr);

    return 0;
}

이렇게 화살표로 구조체 포인터를 표현하여 구조체 멤버의 값을 자유롭게 바꿀 수 있다.

동적 메모리 할당

프로그램 실행중(RunTime)에 메모리를 할당 받는 것.

이걸 왜 할까?
배열이나 구조체 크기를 컴파일 타임에 알 수 없을 경우 사용(사용자 입력을 받는 경우)

함수	기능	특징
`malloc(n)`	n바이트 할당	초기화 X (쓰레기값)
`calloc(n, size)`	n개 × size 크기 할당	0으로 초기화
`realloc(ptr, new_size)`	기존 ptr 메모리 크기 변경	기존 값 유지됨
`free(ptr)`	할당된 메모리 해제	안 하면 메모리 누수

B Tree 삽입 삭제

B Tree?
Balanced Tree, 이진트리에서 더 나아가, 한 노드가 자식을 2개 이상 가질 수 있는 트리

이런 경우 한 노드가 5개의 포인터를 갖는 5차 B Tree 라고 한다.

기본용어
만약 M차 B Tree 라면 각 노드는
최대 키는 M - 1 개를 가질 수 있고, 최소 Key는 Math.ceil(M/2) - 1 개를 가질 수 있다.

즉 위 예시처럼 5차 B Tree 라면 각 노드마다 2~ 4개의 키를 가질 수 있다.
이 기본 용어가 이해된 상태라면 삽입과 삭제가 어렵지 않다.

삽입

만약 위 예시에서 4를 삽입한다고 하자.
1. BigNode 만들기
BigNode란 말 그대로 최대 키 개수를 초과하는 노드를 말한다. 4를 집어넣게 된다면 1 2 4 5 6 이란 Big Node가 만들어지게 된다

BigNode 분할 및 재배치(redistribution)
그럼 양쪽 끝을 left, Right 가운데를 Center 라고 했을때, Center는 부모 노드로 재배치하고, Center를 기준으로 왼쪽과 오른쪽으로 분할하게 된다.
만약 Center를 부모 노드로 재배치 했는데 부모 노드 역시 BigNode가 된다면 위 과정을 부모노드에서 반복하면 된다.

삭제

위 예시에서 만약 12를 삭제한다고 하자.

삭제시 최소 키 개수를 만족하는지 체크
12를 지우게 되면 해당 노드에 9라는 키 하나만 남기때문에 최소 키 개수인 2개보다 작아지게 된다.
그렇다면 형제 노드에서 키를 빌릴 수 있는지 확인
형제 노드 중 하나가 최소 키 개수보다 많은 키를 갖는 지 확인.
즉 남은 노드 + 부모의 중간 노드 + 형재 노드를 한 노드에 넣고 가운데를 기준으로 두 부분으로 나누어 재배치
근데 재배치가 안되는 경우도 있다.
형제 노드도 빌려줄 키가 없고, 부모 역시 빌려줄 키가 없다면 이를 Merge 해야한다.