트라이(Trie)

트라이(Trie)

개념

 

문자열의 집합을 표현하는 트리 자료구조

문자열의 검색을 빠르게 해주는 자료구조 

 

사용 목적

 

두 문자열을 비교하는 경우엔 단순한 비교를 통해 진행하기 때문에 문자열의 길이만큼 시간 소요 

=> 문자열의 길이 O(M) * 문자열의 총 개수 O(logN) => O(Mlog(N))

 

특징

트라이(Trie) 자료구조 예시

• 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 문자열의 접두사를 얻을 수 있다.
• 리프 노드의 개수는 문자열의 총 개수와 동일하다.

 

장단점

 

장점

• 문자열 추가와 탐색이 모두 O(M)만에 가능

단점

• 각 노드가 자식에 대한 포인터를 저장하므로 메모리가 많이 필요

 

사용 예시

• 검색어 자동완성, 사전에서 단어 찾기, 문자열 검사

 

참고

https://nooblette.tistory.com/entry/%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie

트라이(Trie)