트라이(trie) 자료구조

문자의 효율적 탐색을 위한 트리형태의 자료구조 루트부터 트리를 타고 가 리프에 다달으면 해당 경로의 문자가 저장되어 있음을 의미 사용이유 단순 문자 비교들 통한 탐색의 시간 복잡도는 높기에 효율적인 탐색을 위해 사용 시간 복잡도 생성: O(len(string) + total_num(string)) 탐색: O(len(string)) ex) ba, abcd, ac ba 첫 문자는 b이다. trie자료구조에는 아무 정보가 없기에 루트의 child로 b추가 b의 child가 없기에 b에 a를 추가 abcd 루트의 child에 a가 없기에 루트의 child로 a추가 a의 child로 존재하는 b는 trie에 없기에 a의 child로 b추가 c를 b의 child로 추가 d를 c로 child로 추가 ac 루트의 child에 a가 존재하므로 a의 c..........

원문링크 : 트라이(trie) 자료구조