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

트라이(Trie)란?

• 문자열을 빠르게 탐색할 수 있는 자료구조
• 길이가 L인 문자열을 이진탐색하면 O(LlogN)이지만, 트라이 구조를 활용하면 O(M)로 더 효율적이다.

trie 구조 - 위키백과

---

트라이(Trie) 구현

Node 구현

• key : 입력될 값
• data : 문자열의 종료 표시 (문자열 전체)
• child : 자식 노드

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

---

Trie 구현

• class 초기화
  • 비어있는 node 생성

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

 

• 삽입(insert) 구현
  • 문자열을 한 글자씩 child에 저장하고, 마지막에는 해당 문자열 전체를 저장한다.

    def insert(self, string):
        cur_node = self.head
        for char in string:
            if char not in cur_node.child:
                cur_node.child[char] = Node(char)
            cur_node = cur_node.child[char]
        cur_node.data = string

 

• 검색(search) 구현
  • 문자열의 한 글자씩 node의 child에 존재하는지 확인하고, 마지막에 해당 문자열이 저장되어 있다면 True를 반환한다.

    def search(self, string):
        cur_node = self.head
        for char in string:
            if char in cur_node.child:
                cur_node = cur_node.child[char]
            else:
                return False
        if cur_node.data != None:
            return True
        else:
            return False

---

Trie 삽입 및 삭제

trie = Trie()
trie.insert('apple')
trie.insert('app')

print(trie.search('apple'))
print(trie.search('appp'))

# True
# False