Trie 자료구조
- 트리 기반
- 각 트리 노드에 1개 이상의 글자가 저장됨
- 특정 prefix에 따라 특정 값을 얻고 싶을 때 사용함
- 삽입
- 삽입할 단어의 첫 글자부터 순회하며 루트 노드부터 시작함
- 현재 글자에 해당하는 자식 노드가 없으면 새 노드를 생성함
- prefix가 일치하는 자식 노드로 이동 후 다음 글자를 처리함
- 마지막 글자 노드에 ‘단어 종료’ 표시(flag)를 설정하거나 값을 저장함
- 시간 복잡도: 삽입할 단어 길이 L에 대해 O(L)
- 검색
- 루트 노드부터 시작해서 글자 패턴이 매칭되는 자식 노드로 이동함
- 더 이상 매칭되지 않을 때까지 이동한 후 값을 얻음
- 시간 복잡도: 검색할 문자열 길이 N에 대해 O(N)
- 장점
- 검색 제안어 생성할 때 prefix 단위로 탐색하여 시간 복잡도 측면에서 유리함
ㄴ(M: 전체 문자열 길이, N: 검색할 문자열 길이)시간복잡도 String.prototype.search()Trie 생성 O(M) O(M) 검색 O(M+N) O(N)
- 검색 제안어 생성할 때 prefix 단위로 탐색하여 시간 복잡도 측면에서 유리함
- 단점
String.prototype.search()함수에 비해 메모리 사용량이 많음
이유와 방법을 알려주는 메모장 겸 블로그 (Frontend, AI, 경제, 책)