[스터디] Trie

📍Trie

🔎 Trie 정의

• retrieval tree에서 나온 단어이다.
• 문자열의 집합을 표현하는 트리 자료구조
• 문자열을 탐색하는데 특화 (자동완성 기능, 사전 검색 등)
• 래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 한다.

🔎 Trie 사용 이유

원하는 원소를 찾기 위해 사용되는 이진 검색 트리 등에서는 원소를 찾는데 O(logN)의 시간이 걸리게 된다.
하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 이러한 문제를 해결하기 위해 Trie을 사용한다.

🔎 Trie 원리

• r -> re -> reb -> rebr -> rebro의 순서로 탐색되므로 "rebro"의 모든 접두사들이 다 구해지게 된다.
  

• 한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색으로 나타낸 리프 노드는 문자열의 끝을 의미한다.
• 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면, 찾고자 하는 문자열의 접두사를 얻을 수 있다.

🔎 Trie 장단점

• 장점
  • 문자열 검색이 빠르다
  • 문자열 추가와 탐색이 O(M)만에 가능하다. -> 시간복잡도에서 효율적
• 단점
  • 필요 메모리의 크기가 크다

🔎 Trie 시간복잡도

가장 긴 문자열의 길이를 L, 총 문자수를 M이라고 할 때,

• 생성 시간 복잡도: O(MxL)
• 삽입 시간 복잡도: O(L)
• 탐색 시간 복잡도: O(L)
  
  

📍스터디 회고

🔎 아쉬운 점

생각보다 공부할 내용이 많아서 자세하게 하지 못한게 아쉬웠다.
추가로 더 공부해 봐야겠다.

🔎 추가로 알게 된 내용

🔎 추가로 공부할 내용

📍공부한 곳

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
https://velog.io/@klloo/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0