Trie (트라이, Digital tree, prefix, Retrieval tree) + 예제 코드

Trie 란?

: 탐색트리의 일종으로 동적 집합이나 연관배열을 저장하는데 사용되는 트리 자료 구조 (출처: 위키백과)

 

**문자열, 접두사와 관련된 검색에 매우 유용하게 사용됨

 

wikipedia

 

---

 

Leetcode의 Trie관련 문제를 통해서 더 자세히 알아봅시다!

 

https://leetcode.com/problems/implement-trie-prefix-tree/

Implement Trie (Prefix Tree) - LeetCode

 

 

---

예시 답안 풀이)

 

Discussion에 있는 풀이를 가지고 와봤는데요

 

class TrieNode:
    def __init__(self):
        self.word = None
        self.children = {}

 

insert에서는 포도송이를 만든다고 생각하면 좀 이해가 빠른데요

node의 이미 필요한 문자가 없으면, children에 node를 추가하는거죠

 

search는 node = node.children[c]로 계속 Trie를 타고 내려가다가 찾는 문자가 없으면  False를 반환하도록 합니다

 

class Trie:   
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.word = True
 
 --------------------------------------------------------------

    def search(self, word: str) -> bool:
        node = self.root
        for c in word:
            if c in node.children:
                node = node.children[c]
            else:
                return False
        return node.word

 --------------------------------------------------------------

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for i in prefix:
            if i in node.children:
                node = node.children[i]
            else:
                return False
        return True

 

코드가 명료해서 이해가 잘되지만 Trie 관련 다른 코드들도 보면서 더 알아볼 수 있으면 좋을 것 같네요!