[C/C++] 트라이 (Trie)

문자열 탐색을 위한 트리 구조를 가진 알고리즘

• 문자 탐색 트리(Tree)
• 탐색 속도 O(log_2(n))
• 사이즈 문자열길이^len << big problem

코드

// consider only lowercase alphabet
#include <stdio.h>
#include <iostream>
using namespace std;

#define ALPHABET_SIZE 26
#define convertCharToIndex(c) c - 'a'

template <typename T>
int strlen(T* type) {
    int i = -1;
    while(type[++i] != 0);
    return i;
}

class TrieNode {
public:
    bool valid;
    TrieNode *children[ALPHABET_SIZE];
    TrieNode() {
        valid = false;
        for(int i = 0; i< ALPHABET_SIZE; ++i) {
            children[i] = 0;
        }
    }
    // ~TrieNode(); // need to implement
};

class Trie {
public:
    TrieNode *head;
    Trie() {
        head = new TrieNode();
    }
    // ~Trie(); // need to implement
    void insert(const char* str);
    bool find(const char* str);
};


void Trie::insert(const char* str) {
    TrieNode *current = head;
    int i = -1;
    while(str[++i] != 0) {
        int index = convertCharToIndex(str[i]);
        if(!current->children[index]) {
            current->children[index] = new TrieNode;
        }
        current = current->children[index];
    }
    current->valid = true;
}

bool Trie::find(const char* str) {
    TrieNode *current = head;
    int i = -1;
    while(str[++i] != 0) {
        int index = convertCharToIndex(str[i]);
        if(!current->children[index]) {
            return false;
        }
        current = current->children[index];
    }
    return current->valid;
}

int main() {
     const char* keys[] = {"the", "a", "there",
                    "answer", "any", "by",
                     "bye", "their" };
    int keyslen = strlen(keys);

    Trie trie = Trie();
    for (int i = 0; i < keyslen; ++i) {
        trie.insert(keys[i]);
    }
    printf("the? ");
    trie.find("the")? cout << "Yes\n" : cout << "No\n";
    
    printf("these? ");
    trie.find("these")? cout << "Yes\n" : cout << "No\n";
    return 0;
}

result