[자료구조] Trie

Trie란?

문자열의 집합을 표현하는 트리 자료구조
원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리에서 문자열을 찾는 경우 O(MlogN)이 걸림
여러번 수행 시 시간이 오래걸리게 됨
그래서 이 단점을 해결한 문자열을 찾는데에 특화된 자료구조가 Trie다.

작동 원리
집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리
한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색으로 나타낸 노드는 문자열의 끝을 의미함
ex> rebro : r->re->reb->rebr->rebro
문자열의 추가 탐색 모두 O(M)만에 가능함

단점
필요한 메모리의 크기가 너무 큼
총 메모리 : O(포인터 크기x포인터 배열 개수x노드의 개수)

🫠

출처: https://rebro.kr/86