키 트리는 문자열이나 키 값을 효율적으로 저장하고 검색하기 위해 사용되는 특수한 형태의 트리 자료구조입니다. 주로 자동 완성 기능, 사전 애플리케이션, IP 라우팅 테이블 등 문자열 기반의 빠른 검색 성능이 중요한 분야에서 활용됩니다. 키 트리는 키를 구성하는 각 문자를 노드에 저장하며, 이 노드들이 연결되어 전체 키를 나타내는 경로를 형성합니다. 이러한 구조 덕분에 키의 접두어(prefix)를 공유하는 키들이 효율적으로 저장될 수 있습니다.

키 트리를 구현하는 두 가지 주요 방식에 대해 살펴보겠습니다: 이중 연결 키 트리(Double-Linked Key Tree)와 트라이(Trie Tree).

이중 연결 키 트리(Double-Linked Key Tree)

이중 연결 키 트리는 각 노드가 자체 문자(character), 첫 번째 자식 노드를 가리키는 포인터(firstChild), 그리고 다음 형제 노드를 가리키는 포인터(nextSibling)를 포함하는 구조입니다. 키의 끝에 해당하는 잎(leaf) 노드는 해당 키와 연결된 실제 데이터를 가리키는 포인터(dataPointer)를 가집니다. 이 구조는 자식-형제 표현 방식과 유사하여 메모리 사용 측면에서 효율적일 수 있습니다.

다음은 이중 연결 키 트리의 C 언어 구현 예시입니다. 이 구현은 키의 삽입, 검색, 순회 및 트리 소멸 기능을 포함합니다.

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

#define MAX_KEY_LENGTH 16
#define END_OF_KEY '\0' // 키의 끝을 나타내는 문자

// 레코드의 추가 데이터 구조체
typedef struct
{
    int order;
} AuxiliaryData;

// 키 정보 구조체
typedef struct
{
    char characters[MAX_KEY_LENGTH];
    int length;
} KeyInfo;

// 실제 저장될 레코드 구조체
typedef struct
{
    KeyInfo key;
    AuxiliaryData data;
} DataRecord;

// 노드 종류 열거형
typedef enum { LEAF_NODE, BRANCH_NODE } NodeType;

// 이중 연결 키 트리 노드 구조체
typedef struct DLinkedTreeNode
{
    char character;             // 현재 노드가 나타내는 문자
    struct DLinkedTreeNode *nextSibling; // 다음 형제 노드를 가리키는 포인터
    NodeType type;              // 노드 종류 (잎 노드 또는 가지 노드)
    union
    {
        DataRecord *dataPointer;    // 잎 노드일 경우 레코드 포인터
        struct DLinkedTreeNode *firstChild; // 가지 노드일 경우 첫 자식 포인터
    } ptr;
} DLinkedTreeNode, *DLinkedTree;

// 빈 이중 연결 키 트리 초기화
void initializeTree(DLinkedTree *tree)
{
    *tree = NULL;
}

// 레코드 내용을 출력하는 함수
void printRecord(DataRecord record)
{
    printf("(%s, %d) ", record.key.characters, record.data.order);
}

// 이중 연결 키 트리에서 키를 검색하는 함수
// 키에 해당하는 레코드를 찾으면 포인터를 반환하고, 없으면 NULL을 반환
DataRecord *searchTree(DLinkedTree tree, KeyInfo searchKey)
{
    DLinkedTreeNode *current = tree;
    int charIndex = 0;

    while (current != NULL && charIndex < searchKey.length)
    {
        // 현재 레벨에서 searchKey[charIndex]와 일치하는 형제 노드를 찾음
        while (current != NULL && current->character != searchKey.characters[charIndex])
        {
            current = current->nextSibling;
        }

        if (current != NULL)
        {
            // 일치하는 노드를 찾았으면 다음 문자를 위해 자식 노드로 이동
            current = current->ptr.firstChild;
            charIndex++;
        }
        else // 현재 문자와 일치하는 노드를 찾지 못함
        {
            return NULL;
        }
    }

    // 모든 문자를 따라왔을 때, current는 잎 노드를 가리켜야 하며
    // 잎 노드의 character는 END_OF_KEY여야 함
    if (current != NULL && current->type == LEAF_NODE && current->character == END_OF_KEY)
    {
        return current->ptr.dataPointer;
    }
    return NULL;
}

// 이중 연결 키 트리에 레코드를 삽입하는 함수
void insertIntoTree(DLinkedTree *tree, DataRecord *recordToInsert)
{
    DLinkedTreeNode *current = *tree;
    DLinkedTreeNode *parentNode = NULL; // 삽입될 노드의 부모가 될 노드
    DLinkedTreeNode *prevSibling = NULL; // 새 노드의 이전 형제가 될 노드
    int charIndex = 0;
    KeyInfo key = recordToInsert->key;

    // 트리가 비어있는 경우, 새 트리를 구성
    if (*tree == NULL)
    {
        DLinkedTreeNode *newNode;
        for (; charIndex < key.length; ++charIndex)
        {
            newNode = (DLinkedTreeNode *)malloc(sizeof(DLinkedTreeNode));
            if (newNode == NULL) exit(EXIT_FAILURE);
            newNode->character = key.characters[charIndex];
            newNode->type = BRANCH_NODE;
            newNode->nextSibling = NULL;
            newNode->ptr.firstChild = NULL;

            if (parentNode != NULL) // 이전 노드가 현재 노드의 부모
            {
                parentNode->ptr.firstChild = newNode;
            }
            else // 루트 노드
            {
                *tree = newNode;
            }
            parentNode = newNode;
        }

        // 키의 끝을 나타내는 잎 노드 생성
        newNode = (DLinkedTreeNode *)malloc(sizeof(DLinkedTreeNode));
        if (newNode == NULL) exit(EXIT_FAILURE);
        newNode->character = END_OF_KEY; // 잎 노드 마커
        newNode->type = LEAF_NODE;
        newNode->nextSibling = NULL;
        newNode->ptr.dataPointer = recordToInsert;
        parentNode->ptr.firstChild = newNode;
        return;
    }

    // 트리가 비어있지 않은 경우, 삽입 위치를 찾음
    parentNode = NULL;
    prevSibling = NULL;
    current = *tree;
    charIndex = 0;

    while (current != NULL && charIndex < key.length)
    {
        // 현재 레벨에서 키 문자 순서에 맞춰 삽입 위치를 찾음
        while (current != NULL && current->character < key.characters[charIndex])
        {
            prevSibling = current;
            current = current->nextSibling;
        }

        if (current != NULL && current->character == key.characters[charIndex])
        {
            // 일치하는 문자를 찾았으면, 다음 문자를 위해 자식으로 내려감
            parentNode = current;
            prevSibling = NULL; // 자식 레벨에서는 이전 형제가 없음
            current = current->ptr.firstChild;
            charIndex++;
        }
        else // 일치하는 문자를 찾지 못했거나 현재 위치에 삽입해야 함
        {
            break; // 현재 charIndex부터 새 경로를 삽입해야 함
        }
    }
    
    // 이미 존재하는 키라면 삽입하지 않음 (이중 삽입 방지)
    if (charIndex == key.length && current != NULL && current->type == LEAF_NODE && current->character == END_OF_KEY) {
        // 이미 해당 키가 존재하므로 삽입하지 않음 (또는 데이터 업데이트)
        return;
    }

    // charIndex부터 키의 나머지 부분을 새로운 노드로 삽입
    DLinkedTreeNode *newNode, *tempNode;

    // 새로운 경로의 첫 번째 노드 생성 (현재 문자에 해당)
    newNode = (DLinkedTreeNode *)malloc(sizeof(DLinkedTreeNode));
    if (newNode == NULL) exit(EXIT_FAILURE);
    newNode->character = key.characters[charIndex];
    newNode->type = BRANCH_NODE;
    newNode->ptr.firstChild = NULL; // 자식은 나중에 연결
    newNode->nextSibling = current; // 현재 위치의 노드를 새 노드의 형제로 연결

    // 새 노드를 부모 또는 형제에 연결
    if (parentNode == NULL) // 루트 레벨에 삽입
    {
        if (prevSibling == NULL) // 루트가 새 노드보다 크거나 루트가 비어있었음
        {
            *tree = newNode;
        }
        else // 루트의 형제 체인에 삽입
        {
            prevSibling->nextSibling = newNode;
        }
    }
    else // 중간 레벨에 삽입
    {
        if (prevSibling == NULL) // 첫 자식 위치에 삽입
        {
            parentNode->ptr.firstChild = newNode;
        }
        else // 형제 체인에 삽입
        {
            prevSibling->nextSibling = newNode;
        }
    }
    
    tempNode = newNode; // 새로운 경로의 현재 노드 포인터
    charIndex++; // 다음 문자부터 처리

    // 나머지 키 문자에 대해 가지 노드를 생성하여 연결
    for (; charIndex < key.length; ++charIndex)
    {
        newNode = (DLinkedTreeNode *)malloc(sizeof(DLinkedTreeNode));
        if (newNode == NULL) exit(EXIT_FAILURE);
        newNode->character = key.characters[charIndex];
        newNode->type = BRANCH_NODE;
        newNode->nextSibling = NULL;
        newNode->ptr.firstChild = NULL;
        tempNode->ptr.firstChild = newNode;
        tempNode = newNode;
    }

    // 마지막으로 잎 노드 생성 및 연결
    newNode = (DLinkedTreeNode *)malloc(sizeof(DLinkedTreeNode));
    if (newNode == NULL) exit(EXIT_FAILURE);
    newNode->character = END_OF_KEY;
    newNode->type = LEAF_NODE;
    newNode->nextSibling = NULL;
    newNode->ptr.dataPointer = recordToInsert;
    tempNode->ptr.firstChild = newNode;
}

// 이중 연결 키 트리를 깊이 우선 방식으로 순회하는 함수
void traverseDLinkedTree(DLinkedTree tree, void (*visit)(DataRecord))
{
    if (tree == NULL)
        return;

    // 잎 노드에 도달하고 키의 끝을 나타내면 레코드 출력
    if (tree->type == LEAF_NODE && tree->character == END_OF_KEY)
    {
        visit(*(tree->ptr.dataPointer));
    }
    
    // 자식 노드를 먼저 탐색 (깊이 우선)
    if (tree->type == BRANCH_NODE && tree->ptr.firstChild != NULL)
    {
        traverseDLinkedTree(tree->ptr.firstChild, visit);
    }

    // 형제 노드를 탐색
    if (tree->nextSibling != NULL)
    {
        traverseDLinkedTree(tree->nextSibling, visit);
    }
}

// 이중 연결 키 트리의 모든 노드를 소멸시키는 함수 (깊이 우선)
void destroyTree(DLinkedTree *tree)
{
    if (*tree == NULL)
        return;

    // 자식 노드를 먼저 소멸
    if ((*tree)->type == BRANCH_NODE && (*tree)->ptr.firstChild != NULL)
    {
        destroyTree(&(*tree)->ptr.firstChild);
    }
    // 형제 노드를 소멸
    if ((*tree)->nextSibling != NULL)
    {
        destroyTree(&(*tree)->nextSibling);
    }

    // 현재 노드 메모리 해제
    free(*tree);
    *tree = NULL;
}

트라이(Trie Tree)

트라이(Trie)는 '접두어 트리(Prefix Tree)'라고도 불리며, 키의 각 문자를 노드에 저장하고 특정 노드까지의 경로가 하나의 키 접두어를 나타내는 계층적 트리 구조입니다. 이중 연결 키 트리와 다르게, 트라이는 각 가지 노드에 문자를 명시적으로 저장하기보다는, 부모 노드의 자식 포인터 배열의 인덱스가 해당 문자를 나타내도록 설계되는 경우가 많습니다. 예를 들어, 소문자 영어 알파벳만을 처리하는 트라이는 각 노드가 26개의 자식 포인터 배열을 가질 수 있습니다. 단어가 끝나는 노드에는 해당 단어의 완료 여부와 실제 레코드에 대한 포인터가 저장될 수 있습니다.

다음은 트라이 트리의 C++ 언어 구현 예시입니다. 이 구현은 소문자 영어 알파벳만을 처리하며, 각 문자에 해당하는 자식 노드는 배열 인덱스로 접근합니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // for std::tolower

#define ALPHABET_SIZE 26 // 소문자 영어 알파벳 (a-z)

// 레코드의 추가 데이터 구조체
struct AuxiliaryData {
    int order;
};

// 실제 저장될 레코드 구조체
struct DataRecord {
    std::string key;
    AuxiliaryData data;
};

// 트라이 노드 구조체
struct TrieNode {
    // 자식 노드를 가리키는 포인터 배열 (알파벳 크기만큼)
    TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord; // 이 노드에서 단어가 끝나는지 여부
    DataRecord* recordPtr; // 단어가 끝나는 경우 해당 레코드 포인터

    // 생성자: 자식 포인터를 nullptr로 초기화
    TrieNode() : isEndOfWord(false), recordPtr(nullptr) {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            children[i] = nullptr;
        }
    }

    // 소멸자: 모든 자식 노드를 재귀적으로 해제
    ~TrieNode() {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            delete children[i]; // 자식 노드가 nullptr이면 delete는 아무 작업도 하지 않음
        }
        // recordPtr가 가리키는 DataRecord는 보통 트라이 외부에서 관리되므로 여기서 해제하지 않음
        // 필요하다면 여기서 delete recordPtr; 를 추가할 수 있음 (단, DataRecord가 동적 할당된 경우)
    }
};

// 트라이 클래스
class Trie {
private:
    TrieNode* root;

    // 문자를 0-25 범위의 인덱스로 변환 (소문자 'a'를 0으로 매핑)
    int charToIndex(char c) {
        return std::tolower(c) - 'a';
    }

    // 특정 노드 아래의 모든 단어와 레코드를 수집하는 재귀 함수
    void collectWords(TrieNode* node, std::vector<DataRecord*>& results) {
        if (node == nullptr) return;

        if (node->isEndOfWord && node->recordPtr != nullptr) {
            results.push_back(node->recordPtr);
        }

        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            if (node->children[i] != nullptr) {
                collectWords(node->children[i], results);
            }
        }
    }

public:
    // 생성자: 루트 노드 초기화
    Trie() {
        root = new TrieNode();
    }

    // 소멸자: 루트 노드를 삭제하여 모든 하위 노드 재귀적으로 해제
    ~Trie() {
        delete root;
    }

    // 단어를 트라이에 삽입
    void insert(const std::string& key, DataRecord* record) {
        TrieNode* current = root;
        for (char c : key) {
            int index = charToIndex(c);
            if (index < 0 || index >= ALPHABET_SIZE) {
                std::cerr << "Error: Invalid character '" << c << "' for Trie. Skipping key: " << key << std::endl;
                return; // 유효하지 않은 문자 처리
            }
            if (current->children[index] == nullptr) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        current->isEndOfWord = true;
        current->recordPtr = record;
    }

    // 트라이에서 단어를 검색
    // 단어를 찾으면 해당 레코드 포인터를 반환하고, 없으면 nullptr 반환
    DataRecord* search(const std::string& key) {
        TrieNode* current = root;
        for (char c : key) {
            int index = charToIndex(c);
            if (index < 0 || index >= ALPHABET_SIZE || current->children[index] == nullptr) {
                return nullptr; // 경로가 존재하지 않음
            }
            current = current->children[index];
        }
        return current != nullptr && current->isEndOfWord ? current->recordPtr : nullptr;
    }

    // 특정 접두어를 가진 모든 단어를 찾아 벡터로 반환
    std::vector<DataRecord*> findWordsWithPrefix(const std::string& prefix) {
        std::vector<DataRecord*> results;
        TrieNode* current = root;
        for (char c : prefix) {
            int index = charToIndex(c);
            if (index < 0 || index >= ALPHABET_SIZE || current->children[index] == nullptr) {
                return results; // 접두어 경로가 존재하지 않음
            }
            current = current->children[index];
        }
        
        // 접두어 노드부터 모든 하위 단어를 재귀적으로 탐색하여 수집
        collectWords(current, results);
        return results;
    }
};