**trie(트라이, prefix tree, 접두사 트리)**는 각 간선이 하나의 문자를 나타내고, 루트로부터의 각 경로가 하나의 접두사를 이루는 트리입니다. 접두사를 공유하는 단어들은 같은 경로를 공유하므로, 접두사 조회가 극도로 빠릅니다.
구조
text
"cat", "car", "dog" 삽입:
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* 는 단어의 끝을 표시)
코드
python
:
():
.children = {}
.is_end =
:
():
.root = TrieNode()
():
node = .root
ch word:
node = node.children.setdefault(ch, TrieNode())
node.is_end =
():
node = .root
ch prefix:
ch node.children:
node = node.children[ch]
