Kim Jinung

Trie 본문

Computer Science/Data Structure

Trie

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 등이라는 용어로도 불린다.

구현은 쉬운데.. 응용해서 사용하는 것이 현재로써는 마냥 쉽지는 않은 너낌..

'Computer Science > Data Structure' 카테고리의 다른 글

Self-Balancing Binaray Search Tree - (AVL tree, Red-Balck Tree)  (0) 2022.12.12
Abstract data type(ADT)  (0) 2022.12.08
Heap  (0) 2022.12.08
'Computer Science/Data Structure' Related Articles more