[자료구조] 트라이(Trie)에 대해 설명해주세요.

💡 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 찾고자 하는 문자열의 길이가 시간 복잡도가 됩니다. 즉, 문자열의 길이가 m이라면 시간 복잡도는 O(m).

문자열에 대해 이진탐색트리를 적용하면 O(Mlog(N))의 시간복잡도.

트라이를 이용하면 O(M)의 시간복잡도로 탐색이 가능하다.

Reference
https://nooblette.tistory.com/entry/%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie