트라이 (Trie)
문자열을 빠르게 검색할 수 있는 K진 트리 구조의 자료구조
단어 사전을 트라이로 생성한 후 찾을 단어가 생기면 트라이를 사용하여 검색한다.
트라이의 루트 노드는 항상 공백문자열 상태를 의미한다.
트라이에 단어 삽입하기
- 루트 노드부터 시작하여 삽입할 단어의 첫 글자부터 트라이를 탐색
- 만약 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면 해당하는 자식 노드로 이동하고, 없다면 새로운 자식을 추가
- 단어를 삽입한 후에, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가
트라이에 존재하는 가장 긴 문자열의 길이를 L이라 하고 총 문자열들의 수를 M이라 하자.
처음 트라이를 구축할 때에는 M개에 대해서 L만큼 걸리기 때문에 수행시간은 \(O(L \times M)\) 이다.
그 후에 새로운 문자열을 추가할 때에는 \(O(L)\) 만큼 걸린다.
트라이를 이용하여 검색하기
- 루트 노드부터 시작하여 검색할 단어의 첫 글자부터 트라이를 탐색
- 만약 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면 해당하는 자식 노드로 이동하고, 없다면 검색한 단어는 트라이에 존재하지 않는 단어로 처리
- 탐색이 완료되었다면, 탐색된 마지막 노드의 정보를 이용
트라이에 존재하는 가장 긴 문자열의 길이를 L이라 하고 총 문자열들의 수를 M이라 하자.
트리를 타고 들어가서 L만큼 탐색하기 때문에 수행시간은 \(O(L)\) 이다.
728x90
반응형
'알고리즘 > 자료구조' 카테고리의 다른 글
[백준] 11279번 최대 힙 (JAVA) (0) | 2023.02.28 |
---|---|
[백준] 2042번 구간 합 구하기 (JAVA) (0) | 2023.02.28 |
[CS] 인덱스 트리와 구현 (JAVA) (0) | 2023.02.27 |
[CS] 힙 (0) | 2023.02.24 |
[CS] 이진 트리 (0) | 2023.02.24 |