Trie#

설명#

Trie(트라이, prefix tree)는 문자열의 공통 접두사를 공유하는 트리 기반 자료구조입니다.
각 노드는 문자 하나를 나타내고, 루트에서 어떤 노드까지 내려가는 경로가 하나의 문자열을 표현합니다.

Trie 예시

위의 그림과 같이 tree, trie, tire, tri 를 트라이에 넣으면,
t 와 그 아래의 r 같은 경로는 서로 공유하고, 그 뒤에서 갈라지게 됩니다.

중복되는 접두사를 한 번만 저장하기 때문에, 많은 문자열을 다룰 때도 접두사 검색에 특화됩니다.

활용 예시#

사전, 자동완성
주어진 prefix로 시작하는 모든 단어 찾기 (app검색 -> app, apple, application 등)
정렬된 사전 순 순회
트리 구조를 활용해, 노드를 순회하는 것만으로 자연스럽게 사전 순으로 문자열을 얻을 수 있습니다.

장점#

문자열의 개수와 거의 상관없이,
검색/삽입 시간이 문자열 길이에만 비례합니다.

특히, 많은 문자열 + 접두사 검색이 많은 환경에서 효율적입니다.

단점#

각 문자마다 트리 구성을 위한 노드와 포인터를 가지기 때문에
메모리 사용량이 커질 수 있다는 점이 있고,

문자열이 적거나, 접두사 구조가 잘 공유되지 않는 경우에는
단순 해시 기반 구조가 더 간단하고 효율적일 수 있습니다.

시간 복잡도#

K: 문자열 길이

입력
입력 시에는 각 문자를 따라가며 노드를 생성/이동하기 때문에,
입력하려는 패턴의 문자열의 길이에 따라 $$ O(K) $$ 의 시간 복잡도를 가진다.
검색
검색 시에는 포함된 패턴(단어)의 개수와 무관하게,
검색하려는 문자열의 길이에 따라 내려가기만 하면 되므로 $$ O(K) $$ 의 시간 복잡도를 가진다.

코드#

type Node struct {
	children map[rune]*Node
	isEnd    bool
}  
// newNode 는 Node의 생성자입니다. 
func newNode() *Node {
	return &Node{make(map[rune]*Node), false}
}

type Trie struct {
	root *Node
}
// NewTrie 는 Trie의 생성자입니다. 
func NewTrie() Trie {
	return Trie{newNode()}
}

// Insert 는 Trie 자료구조에 word 문자열을 저장합니다.
func (t Trie) Insert(word string) {
	now := t.root
	for _, char := range word {
		if _, exists := now.children[char]; !exists {
			now.children[char] = newNode()
		}
		now = now.children[char]
	}
	now.isEnd = true
}
// Search 는 Trie 자료구조에서 특정 word 가 저장되어 있는지 확인합니다.
func (t Trie) Search(word string) bool {
	now := t.root
	for _, char := range word {
		if _, exists := now.children[char]; !exists {
			return false
		}
		now = now.children[char]
	}
	return now.isEnd
}

Python

Class Node: 
	def __init__(self): 
		self.child = dict() 
		self.is_end = False 

Class Trie:
	def __init__(self): 
		self.root = Node()

	def insert(self, word):
		 now = self.root 
		 for char in word: 
			 now = now.child.setdefault(char, Node())
		 now.is_end = True 

	 def find(self, word): 
		 now = self.root 
		 for char in word: 
			 if char not in now.child:
				return False 
			now = now.child[char] 
		return now.is_end