LeetCode

[Data Structure] Trie

오늘은 Trie(트라이) 구조에 대해서 알아보고자 합니다. Trie는 기본적으로 Tree(트리) 형태의 자료 구조입니다.접두사 트리(Prefix Tree)라고도 하며, 주로 문자열 데이터를 다룰 때 사용됩니다.특징- Node의 구조에 따라 다르지만, 특이한 점은 자식 Node가 이전 노드(부모 Node)의 값을 일부분을 공유- 각 Node는 하나의 문자(or 접두어)를 저장합니다.- 문자열의 끝을 나타내기 위한 Leaf Node 플래그를 사용합니다.- Trie의 Root Node는 공백 문자 또는 빈 값을 저장합니다.- 검색 및 삽입 Time Complexity는 문자열의 길이에 비례하여 O(M)입니다.(M = 문자열의 길이)구현1. TrieNode 구조체 정의class TrieNode { var ..