[CS] 트라이

트라이 (Trie)

문자열을 빠르게 검색할 수 있는 K진 트리 구조의 자료구조

출처 : https://twpower.github.io/187-trie-concept-and-basic-problem

단어 사전을 트라이로 생성한 후 찾을 단어가 생기면 트라이를 사용하여 검색한다.
트라이의 루트 노드는 항상 공백문자열 상태를 의미한다.
 

트라이에 단어 삽입하기

1. 루트 노드부터 시작하여 삽입할 단어의 첫 글자부터 트라이를 탐색
2. 만약 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면 해당하는 자식 노드로 이동하고, 없다면 새로운 자식을 추가
3. 단어를 삽입한 후에, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가

트라이에 존재하는 가장 긴 문자열의 길이를 L이라 하고 총 문자열들의 수를 M이라 하자.
처음 트라이를 구축할 때에는 M개에 대해서 L만큼 걸리기 때문에 수행시간은 \(O(L \times M)\) 이다.
그 후에 새로운 문자열을 추가할 때에는 \(O(L)\) 만큼 걸린다.
 

트라이를 이용하여 검색하기

1. 루트 노드부터 시작하여 검색할 단어의 첫 글자부터 트라이를 탐색
2. 만약 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면 해당하는 자식 노드로 이동하고, 없다면 검색한 단어는 트라이에 존재하지 않는 단어로 처리
3. 탐색이 완료되었다면, 탐색된 마지막 노드의 정보를 이용

트라이에 존재하는 가장 긴 문자열의 길이를 L이라 하고 총 문자열들의 수를 M이라 하자.
트리를 타고 들어가서 L만큼 탐색하기 때문에 수행시간은 \(O(L)\) 이다.