Data Structure - 5

B-트리, B+트리

B-트리란? 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지는 형태이다.

최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 부른다.

구현하는 조건은

• 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
• 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있습니다.
• 노드의 키가 x개라면 자식의 수는 x+1개 입니다.
• 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족합니다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개입니다.)

B-트리 구현 - C

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

// B-트리 노드 구조
typedef struct BTreeNode {
    int* keys;
    struct BTreeNode** children;
    int num_keys;
    bool is_leaf;
} BTreeNode;

int t_global; // 전역 변수로 차수 관리

// 노드 생성
BTreeNode* create_node(bool is_leaf) {
    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
    node->is_leaf = is_leaf;
    node->num_keys = 0;
    node->keys = (int*)malloc(sizeof(int) * (2 * t_global - 1));
    node->children = (BTreeNode**)malloc(sizeof(BTreeNode*) * (2 * t_global));
    for (int i = 0; i < 2 * t_global; i++) {
        node->children[i] = NULL;
    }
    return node;
}

// 중위 순회
void traverse(BTreeNode* root) {
    if (root != NULL) {
        for (int i = 0; i < root->num_keys; i++) {
            if (!root->is_leaf) traverse(root->children[i]);
            printf("%d ", root->keys[i]);
        }
        if (!root->is_leaf) traverse(root->children[root->num_keys]);
    }
}

// 키 탐색
BTreeNode* search(BTreeNode* node, int key) {
    int i = 0;
    while (i < node->num_keys && key > node->keys[i]) i++;
    if (i < node->num_keys && key == node->keys[i]) return node;
    if (node->is_leaf) return NULL;
    return search(node->children[i], key);
}

// 자식 분할
void split_child(BTreeNode* parent, int i, BTreeNode* y) {
    int t = t_global;
    BTreeNode* z = create_node(y->is_leaf);
    z->num_keys = t - 1;

    // 오른쪽 절반 키 복사
    for (int j = 0; j < t - 1; j++)
        z->keys[j] = y->keys[j + t];

    // 자식 포인터도 복사
    if (!y->is_leaf) {
        for (int j = 0; j < t; j++)
            z->children[j] = y->children[j + t];
    }

    y->num_keys = t - 1;

    // 부모에 자식 삽입
    for (int j = parent->num_keys; j >= i + 1; j--)
        parent->children[j + 1] = parent->children[j];
    parent->children[i + 1] = z;

    // 부모에 키 삽입
    for (int j = parent->num_keys - 1; j >= i; j--)
        parent->keys[j + 1] = parent->keys[j];
    parent->keys[i] = y->keys[t - 1];
    parent->num_keys++;
}

// 삽입 (full 노드 제외)
void insert_non_full(BTreeNode* node, int key) {
    int i = node->num_keys - 1;

    if (node->is_leaf) {
        // 오른쪽으로 이동하면서 자리 찾기
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->num_keys++;
    } else {
        while (i >= 0 && key < node->keys[i]) i--;
        i++;
        if (node->children[i]->num_keys == (2 * t_global - 1)) {
            split_child(node, i, node->children[i]);
            if (key > node->keys[i]) i++;
        }
        insert_non_full(node->children[i], key);
    }
}

// 삽입 (루트 처리 포함)
void insert(BTreeNode** root_ref, int key) {
    BTreeNode* root = *root_ref;

    if (root->num_keys == (2 * t_global - 1)) {
        BTreeNode* s = create_node(false);
        s->children[0] = root;
        split_child(s, 0, root);
        insert_non_full(s, key);
        *root_ref = s;
    } else {
        insert_non_full(root, key);
    }
}

// 메모리 해제
void free_tree(BTreeNode* root) {
    if (root != NULL) {
        if (!root->is_leaf) {
            for (int i = 0; i <= root->num_keys; i++)
                free_tree(root->children[i]);
        }
        free(root->keys);
        free(root->children);
        free(root);
    }
}

//작접 구현
int main(){
	
}

리프노드는 연결리스트 처럼 옆으로 연결할 수 있다!!

B+트리의 특징으로는 다음과 같습니다.

• index 부분과 leaf 노드로 구성된 순차 data 부분으로 이루어진다.
• Index 부분의 key 값은 leaf에 있는 key 값을 직접 찾아 가는데 사용하고 모든 key 값은 leaf 노드에 나열된다.
  • index 부분의 key 값도 leaf 노드에 다시 한 번 나열된다.
• Leaf 노드는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.
• 노드의 분열이 일어나면 중간 key 값이 부모 노드로 올라간다.
  • 이는 새로 분열된 노드에도 포함되어야 한다.
• 새 노드는 leaf 노드끼리의 linked list에도 삽입되어야 한다.
• 재배치와 합병이 필요하지 않을 때는 leaf 노드에서만 삭제된다.
• leaf node의 값이 삭제되어도 삭제하지 않는다.
  • 다른 key 값을 찾는데 사용될 수 있기 때문
• 재배치할 경우 노드의 key 값은 변하지만 tree 구조는 변하지 않는다.
• 합병을 할 경우 index 부분에서도 key 값을 삭제한다.

B+트리 구현 - C

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

int t_global;

typedef struct BPlusTreeNode {
    int* keys;
    struct BPlusTreeNode** children;
    int num_keys;
    bool is_leaf;
    struct BPlusTreeNode* next; // 리프 노드 간 연결
} BPlusTreeNode;

// 노드 생성
BPlusTreeNode* create_node(bool is_leaf) {
    BPlusTreeNode* node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->is_leaf = is_leaf;
    node->num_keys = 0;
    node->keys = (int*)malloc(sizeof(int) * (2 * t_global - 1));
    node->children = (BPlusTreeNode**)malloc(sizeof(BPlusTreeNode*) * (2 * t_global));
    for (int i = 0; i < 2 * t_global; i++) node->children[i] = NULL;
    node->next = NULL;
    return node;
}

// 탐색
BPlusTreeNode* search(BPlusTreeNode* root, int key) {
    if (root == NULL) return NULL;

    int i = 0;
    while (i < root->num_keys && key > root->keys[i])
        i++;

    if (root->is_leaf) {
        if (i < root->num_keys && root->keys[i] == key)
            return root;
        return NULL;
    }

    return search(root->children[i], key);
}

// 리프에 삽입
void insert_in_leaf(BPlusTreeNode* leaf, int key) {
    int i = leaf->num_keys - 1;
    while (i >= 0 && key < leaf->keys[i]) {
        leaf->keys[i + 1] = leaf->keys[i];
        i--;
    }
    leaf->keys[i + 1] = key;
    leaf->num_keys++;
}

// 자식 분할
void split_child(BPlusTreeNode* parent, int index, BPlusTreeNode* child) {
    int t = t_global;
    BPlusTreeNode* new_child = create_node(child->is_leaf);
    new_child->num_keys = t;

    // 리프일 경우 키 복사 + 연결
    if (child->is_leaf) {
        for (int i = 0; i < t; i++)
            new_child->keys[i] = child->keys[i + t - 1];

        child->num_keys = t - 1;

        new_child->next = child->next;
        child->next = new_child;

        // 부모에 중간값 추가 (리프는 중복 허용)
        for (int i = parent->num_keys; i > index; i--) {
            parent->keys[i] = parent->keys[i - 1];
            parent->children[i + 1] = parent->children[i];
        }

        parent->keys[index] = new_child->keys[0]; // 리프의 첫 키
        parent->children[index + 1] = new_child;
        parent->num_keys++;
    }
    // 내부 노드 분할
    else {
        for (int i = 0; i < t - 1; i++)
            new_child->keys[i] = child->keys[i + t];

        for (int i = 0; i < t; i++)
            new_child->children[i] = child->children[i + t];

        new_child->num_keys = t - 1;
        child->num_keys = t - 1;

        for (int i = parent->num_keys; i > index; i--) {
            parent->keys[i] = parent->keys[i - 1];
            parent->children[i + 1] = parent->children[i];
        }

        parent->keys[index] = child->keys[t - 1];
        parent->children[index + 1] = new_child;
        parent->num_keys++;
    }
}

// 삽입 (비가득 노드)
void insert_non_full(BPlusTreeNode* node, int key) {
    int i = node->num_keys - 1;

    if (node->is_leaf) {
        insert_in_leaf(node, key);
    } else {
        while (i >= 0 && key < node->keys[i])
            i--;
        i++;

        if (node->children[i]->num_keys == 2 * t_global - 1) {
            split_child(node, i, node->children[i]);
            if (key >= node->keys[i])
                i++;
        }
        insert_non_full(node->children[i], key);
    }
}

// 삽입 시작
void insert(BPlusTreeNode** root_ref, int key) {
    BPlusTreeNode* root = *root_ref;
    if (root->num_keys == 2 * t_global - 1) {
        BPlusTreeNode* new_root = create_node(false);
        new_root->children[0] = root;
        split_child(new_root, 0, root);
        insert_non_full(new_root, key);
        *root_ref = new_root;
    } else {
        insert_non_full(root, key);
    }
}

// 중위 순회 (리프만 출력)
void traverse(BPlusTreeNode* root) {
    while (!root->is_leaf)
        root = root->children[0];

    while (root != NULL) {
        for (int i = 0; i < root->num_keys; i++)
            printf("%d ", root->keys[i]);
        root = root->next;
    }
    printf("\n");
}

// 메모리 해제
void free_tree(BPlusTreeNode* node) {
    if (node == NULL) return;

    if (!node->is_leaf) {
        for (int i = 0; i <= node->num_keys; i++)
            free_tree(node->children[i]);
    }

    free(node->keys);
    free(node->children);
    free(node);
}

//직접 구현
int main(){
	
}

트라이 (Trie)

트라이란? 문자열의 집합을 표현하는 트리 자료구조 형태이다.

트라이의 특징은 아래와 같습니다.

• K-진 트리 구조를 통해 문자열을 저장하는 방식.
• 영어 사전의 방식을 그대로 차용함. 만약, game이라는 단어를 찾는다면 사전에서 g부터 a, m, e를 순서대로 찾는 방식을 트리 형태로 구현한 것.
• 즉, 맨 앞의 접두어(prefix)부터 시작하여 단어 전체를 찾아가는 과정.
• Trie는 문자열 저장을 위한 공간을 많이 쓰지만, 탐색에는 매우 효율적이라는 특성이 있습니다.

트라이 구현 - C

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

#define ALPHABET_SIZE 26

// Trie 노드 구조체
typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;  // 이 노드가 단어의 끝인지 여부
} TrieNode;

// 새로운 노드 생성
TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;

    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;

    return node;
}

// 단어 삽입
void insert(TrieNode* root, const char* key) {
    TrieNode* curr = root;
    while (*key) {
        int index = *key - 'a';

        if (curr->children[index] == NULL)
            curr->children[index] = createNode();

        curr = curr->children[index];
        key++;
    }
    curr->isEndOfWord = true;
}

// 단어 검색
bool search(TrieNode* root, const char* key) {
    TrieNode* curr = root;
    while (*key) {
        int index = *key - 'a';
        if (curr->children[index] == NULL)
            return false;

        curr = curr->children[index];
        key++;
    }
    return curr != NULL && curr->isEndOfWord;
}

// 메모리 해제
void freeTrie(TrieNode* root) {
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (root->children[i] != NULL)
            freeTrie(root->children[i]);
    }
    free(root);
}

//직접 구현
int main(){
	
}