트리(Trie)

트리 (Trie)

정의

트라이는 문자열 집합을 표현하는 트리 형태의 자료구조입니다. 각 노드는 하나의 알파벳 문자를 가지며, 루트에서 임의의 노드까지의 경로를 따라가면 해당 경로에 해당하는 문자열을 찾을 수 있습니다.

특징

1. 빠른 검색 속도: 문자열 검색에 (O(n))의 시간 복잡도를 가집니다.
2. 접두어 검색: 접두어가 같은 문자열을 효율적으로 검색할 수 있습니다.
3. 동적 집합 연산: 삽입, 삭제, 검색 등의 연산을 효율적으로 수행할 수 있습니다.

사용 예

1. 문자열 검색: 사전에서 단어를 빠르게 찾는 것과 같은 경우
2. 자동완성: 검색 엔진에서 사용자의 입력에 따른 단어 후보를 빠르게 제시
3. 문자열 집합 관리: 문자열이 많은 경우 이를 효율적으로 저장하고 관리할 수 있습니다.

C와 Python의 비교

C

C에서는 트라이를 다음과 같이 정의할 수 있습니다.

struct TrieNode {
    struct TrieNode* children[26];
    int is_end_of_word;
};

struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    for (int i = 0; i < 26; ++i) {
        node->children[i] = NULL;
    }
    node->is_end_of_word = 0;
    return node;
}

Python

Python에서는 다음과 같이 트라이를 정의할 수 있습니다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

비교

1. 메모리 관리: C는 수동으로 메모리를 관리해야 하지만, Python은 가비지 컬렉션을 지원합니다.
2. 구현의 편의성: Python은 딕셔너리를 통해 더 쉽고 빠르게 트라이를 구현할 수 있습니다.
3. 성능: 일반적으로 C가 Python보다 빠르지만, 최적화된 Python 코드도 충분히 빠를 수 있습니다.
4. 타입 체크: C는 컴파일 타임에 타입을 체크하지만, Python은 동적 타이핑을 지원합니다.

C와 Python 모두 트라이를 구현할 수 있으나, 각 언어의 특성에 따라 특정 상황에서 더 유리한 측면이 있을 수 있습니다. C는 더 높은 성능을 필요로 하는 경우에, Python은 빠른 개발과 유지보수가 중요한 경우에 사용될 수 있습니다.