Trie
-
Trie 자료구조Study/Data Structure 2020. 6. 11. 19:21
https://en.wikipedia.org/wiki/Trie를 참고하면 digital tree 또는 prefix tree라고 하는 trie는 일종의 검색 트리입니다. 동적인 set을 저장하거나 연관있는 배열을 저장할 때 쓰입니다. key는 일반적으로 문자열을 저장합니다. binary search tree와는 다르게 노드는 관련된 키를 저장하지 않습니다. 대신 트리의 위치가 키를 정의하는 방식입니다. 그래서 키는 트리 구조 전체에 분산되어 있습니다. 노드의 모든 하위 항목에는 해당 노드와 연관된 문자열의 공통 접두사가 있습니다. 루트는 빈문자열과 연관되어 있습니다. 위 그림과 같이 "te"의 하위 항목인 "tea", "ted", "ten"은 "te"라는 공통 접두사가 있다고 보시면 됩니다. 아래는 위키피..