[자료구조] 트라이(Trie)

트라이(Trie)는 문자열을 저장하고 빠르게 탐색하기 위해 사용되는 트리 형태의 자료구조입니다.

 

https://csacademy.com/app/graph_editor/

각 노드는 문자를 나타내며, 문자열의 접두사를 공통으로 가지는 경로를 형성합니다.

구현

저는 다음과 같이 구현하였습니다.

#include <bits/stdc++.h>

using namespace std;

typedef struct node {
    char c = '\0';
    bool is_word;
    vector<node *> children;
};

struct Trie {
    node root;

    node *_insert(node *rt, const char *s) {
        if (s[0] == '\0') {
            rt->is_word = true;
            return rt;
        }
        for (node *child : rt->children) {
            if (child->c == s[0]) return _insert(child, &s[1]);
        }
        node *n = new node();
        n->c = s[0];
        rt->children.push_back(n);
        return _insert(n, &s[1]);
    }
    
    node *insert(const char *s) { return _insert(&root, s); }

    node *_search(node *rt, const char *s) {
        if (s[0] == '\0') {
            return rt;
        }
        for (node *child : rt->children) {
            if (child->c == s[0]) {
                return _search(child, &s[1]);
            }
        }
        return NULL;
    }

    node *search(const char *s) {
        node *t = _search(&root, s);
        if (t == NULL || !t->is_word) return NULL;
        return t;
    }

    vector<node *> _prefix_search(node *rt) {
        vector<node *> results;
        if (rt->is_word) results.push_back(rt);
        for (node *child : rt->children) {
            vector<node *> _p = _prefix_search(child);
            results.insert(results.end(), _p.begin(), _p.end());
        }
        return results;
    }
    
    vector<node *> prefix_search(const char *s) {
        node *t = _search(&root, s);
        if (t == NULL) return {};
        return _prefix_search(t);
    }
} trie;

int main() {
    return 0;
}

 

 

• [14426] 접두사 찾기
  굳이 트라이를 쓰지 않아도 되지만, 트라이로 풀 수 있습니다.
• [3178] 코코스
  주어진 문자열을 반으로 잘라서 각각 트라이에 넣고 두 트라이의 노드 수를 합하면 되는 문제입니다.