Trie

• 문자열에서 검색을 빠르게 도와주는 자료구조
• 정수형 이진탐색트리는 O(logN), 문자열에서는 최대길이 M일 때 O(M*logN). 트라이 활용 시,  O(M) 가능
• 자동완성기능, 사전 검색 등 문자열 탐색에 특화됨
• trie == radix tree = prefix tree == retrieval tree
• 각 노드에서 자식들에 대한 포인터들을 배열로 저장하고 있어서 저장공간이 크다.
• Node = key + data + child
• L : 총 문자열의 수, M : 제일 긴 문자열의 길이일 때,
  • 생성 : O(L*M)
  • 탐색 : O(M)

References

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Trie.md

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

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

[자료구조] 트라이 (Trie)