[알고리즘] Trie

Trie 란 ?

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

radix tree 혹은 prefix tree라고도 함

 

 

위와 같은 구조로 조회 시 문자열의 길이만큼의 시간 복잡도를 가진다

검색어 자동완성, 사전에서 찾기, 문자열 검사 등으로 활용된다

O(m) m:문자열 길이

 

---

Trie 구현 소스

 

class Node:
    def __init__(self, key):
        self.key = key
        self.child = dict()
        self.count = 0


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

    def insert(self, word):
        cur = self.head  # 루트를 현재 포인터로 설정

        for ch in word:
            cur.count += 1  # 한 단어 추가될 것이므로 카운트 + 1

            # 만약 ch가 없다면
            if ch not in cur.child:
                cur.child[ch] = Node(ch)  # ch를 key로 갖는 자식 Node 생성
            cur = cur.child[ch]  # 자식 노드로 현재 포인터 이동

        cur.count += 1  # 마지막 노드 카운트 + 1

        # 단어의 끝을 * 로 출력
        if '*' not in cur.child:
            cur.child['*'] = Node('*')

    def searchPrefix(self, word):
        cur = self.head  # 루트를 현재 포인터로 설정

        for ch in word:
            # 만약 ch가 없다면
            if ch not in cur.child:
                return 0
            cur = cur.child[ch]  # 자식 노드로 현재 포인터 이동

        if cur.count > 1:
            return True
        else:
            return False

    def search(self, word):
        cur = self.head  # 루트를 현재 포인터로 설정

        for ch in word:
            # 만약 ch가 없다면
            if ch not in cur.child:
                return False
            cur = cur.child[ch]  # 자식 노드로 현재 포인터 이동

        # 단어의 끝인 * 가 없다면, 없는 단어임 
        if "*" not in cur.child:
            return False
        else:
            return True