TRIE 구조

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.

Trie 는 빠른 시간복잡도를 가지고 있기때문에 검색엔진 사이트에서 제공하는 자동 완성 및 검색어 추천 기능 등 문자열을 탐색하는 곳에서 Trie 알고리즘을 사용합니다.

구조

["frodo", "front", "kakao", "kaggle"]

다음 단어를 trie 구조로 저장한다면 다음과 같은 구조의 트리가 생성 됩니다.

조금더 자세히 구조를 표현하자면 다음과 같습니다.

특징

1. Trie 알고리즘은 노드를 이용한 Tree 형태로 이루어져 있습니다.

2. 문자열의 끝을 알리는 flag가 존재합니다.

저장 코드

head = {}

def add(word):
    node = head
    for w in word:
        if w not in node:
            node[w]={}
        node = node[w]
    node['end'] = True

'ab'라는 문자를 Trie 구조로 데이터를 넣는다면 다음과 같은 순서로 진행됩니다.

1. 'ab'를 for문을 통해 하나씩 집어넣어 주기 위한 for문을 돌립니다.

2. node에 'a'라는 키가 존재하지 않는다면 'a'라는 키를 가진 딕셔너리를 만들어 줍니다.

3. 그리고 node['a'] 딕셔러리의 메모리주소를 node에 넘겨줍니다.

4. node['a']에 'b'라는 키가 존재하지 않는다면 'b'라는 키를 가진 딕셔너리를 만들어 줍니다.

5. 그리고 node['a']['b']의 딕셔러리 메모리주소를 node에 넘겨줍니다.

6. 모든 문자를 넣었기 때문에 for문을 종료합니다

7. 해당 문자열이 끝났다는 표시인 node['end'] = True를 넣어줍니다.

만약 head와 node가 메모리 공간을 공유하는 것이 이해가지 않는다면 먼저 공부하시는 것을 추천드립니다.

찾는 코드

def search(word):
    node = head
    for w in word:
        if w not in node:
            return False
        node = node[w]
    if 'end' in node:
        return True
    else:
        return False

장점

• 트라이(Trie)는 문자열 검색을 빠르게 할 수 있습니다.
• 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적입니다.

단점

• 각 노드에서 자식에 대한 포인터들을 배열로 저장하고 있기때문에 큰 저장 공간을 필요로 합니다.

추천 연습 문제
문자열 집합-백준_실버3