Kim Jinung
2022. 12. 12. 16:29
Trie - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search K-ary search tree data structure This article is about a tree data structure. For the French commune, see Trie-sur-Baïse. TrieTypetreeInvented1960Invented byEdward Fredkin, Axel Thue,
en.wikipedia.org
- 탐색 트리의 일종으로 노드의 자체의 정보를 저장하는 것이 아니라 포지션과 관련된 정보를 저장한다.
- 일반적으로 문자열 색인을 구축하는 형태로, 각 인덱스에 해당하는 character를 Key로 저장한다.
- 따라서 공통 접두사를 가진 문자열의 경우 공통 부모 노드를 가지게 된다.
- digital tree, prefix tree 등이라는 용어로도 불린다.
구현은 쉬운데.. 응용해서 사용하는 것이 현재로써는 마냥 쉽지는 않은 너낌..