Trie 알고리즘 - 파이썬

Trie 알고리즘이란 

---

문자열을 검색을 할때 트리 형식으로 각 단어를 하위 노드에 저장하여 시간 복잡도가 (Mlog(n)) 인 알고리즘 

• 사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다.
• 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다고 위키에 보면 나와있습니다.

 

이 알고리즘을 이용한 문제는 대표적으로 프로그래머스의 가사 검색 문제입니다. 

 

class Node:
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.child = {}


class Trie:
    def __init__(self):
        self.head = Node(None)

    def add(self, string):
        curr_node = self.head

        for char in string:
            if char not in curr_node.child:
                curr_node.child[char] = Node(char)
            curr_node = curr_node.child[char]
        curr_node.data = string

    def search(self, string):
        # 가장 아래에 있는 노드에서 부터 탐색 시작
        curr_node = self.head
        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False
        # 탐색이 끝난 후 해당 노드의 data값이 존재한다면
        # 문자가 포함되어있다는 뜻이다.
        if curr_node.data != None:
            return True