초안 : GGWABaeGi @김민수

2024년 6월 14일 오전 12:00 (GMT+9)

Trie (prefix tree)

정의 및 역사

트라이(prefix tree)는 문자열 모음을 노드 형태로 저장하는 검색 데이터 구조의 일종으로, 각 노드는 문자를 나타낸다.'Trie'라는 단어는 저장된 문자열 내에서 단어나 패턴을 빠르게 검색하는 기능을 가리키는 'retrieval'이라는 용어에서 유래되었다.

트라이는 텍스트 데이터의 하위 문자열을 저장하고 검색하는 효율적인 방법으로 1976년 Ed McCreight에 의해 처음 소개되었습니다. 그 이후로 자동 완성 기능, 맞춤법 검사, 자연어 처리 등 많은 앱의 기본 구성 요소로 자리 잡았습니다.

장점과 단점

array 나 linked list 같은 다른 데이터 구조와 비교할 때 Trie는 몇 가지 장점이 있다.

• 빠른 검색: Trie를 사용하면 저장된 문자열 내에서 특정 단어를 빠르게 검색할 수 있다.
• 효율적인 삽입: Trie에 새 단어를 삽입할 때 O(m) 시간 복잡도(입력된 단어의 길이 만큼)로 삽입할 수 있습니다.
• 공간 효율성: Trie는 각 문자를 한 번만 저장하므로 공간 효율적인 데이터 구조이다.

하지만 고려해야 할 몇 가지 단점이 있다.

• 높은 메모리 사용량: Trie 구조상 더 많은 문자열을 저장할수록 더 많은 메모리를 사용하게 되며 잠재적으로 성능 문제가 발생할 수 있다.
• 복잡성: 특히 대규모 데이터 세트의 경우 트라이를 구현하고 유지 관리하는 것이 복잡할 수 있다.