[자바/자료구조] Trie

Trie(트라이)란?- 트리형 자료구조이다.- 문자열 검색을 효율적으로 저장하고 탐색하기 위해 사용된다.- 중복해서 단어를 저장할 필요가 없다.Trie의 구조루트 노드- 트리의 최상위 노드이며, 보통 빈 값을 가진다.노드- 문자 : 노트가 나타내는 문자- 자식 노드 : 해당 문자의 다음 문자를 나타내는 자식 노트의 리스트- 종료 플래그 : 해당 노드가 문자열의 끝인지 여부를 나타내는 플래그Trie의 주요 연산삽입 (Insert)- 삽입하고자 하는 문자열의 한 글자씩 가져온다.- 트리의 루트부터 적합한 노드 위치를 찾아가면서 저장한다. 이 때, 없으면 새 노드를 생성한다.- 마지막 글자까지 삽입이 되면 isEnd 플래그로 단어의 끝을 표시한다.검색 (Search)- 입력받은 문자열을 한글자씩 파싱(Pars..