자료구조 & 알고리즘
[JAVA/자료구조] 트라이(Trie) 개념, 직접 구현하기
트라이(Trie) 트라이는 문자열을 저장하고, 빠르게 탐색하기 위한 트리 형태의 자료구조이다. 문자열 저장을 위한 메모리를 사용하지만, 탐색속도가 매우 빠르다. O(N) (Java에서 Queue,Stack,List와 다르게 Trie를 직접적으로 구현해놓은 라이브러리는 없다.) 트라이의 형태 Trie에 들어있는 문자열 apple, april bus, busy, beer, best 트라이의 구조(특징) 루트 노드 루트노드는 항상 비어있다. 루트노드의 자식노드는 각 단어들의 첫 글자들이다. endOfWord 표시 파란색으로 칠해져 있는 노드는 각 문자열의 마지막 글자이다. 각 노드 구성 각 노드의 자식노드들을 Map에 저장한다. 해당 노드가 단어의 마지막을 뜻하는 endOfWord를 저장할 boolean형 필..
