[자료구조/알고리즘] Trie 알고리즘

개념 트라이(trie)는 문자열을 빠르게 탐색하게 해주는 자료구조 이다. Trie 알고리을 통해 문자열을 일반적인 string 클래스를 이용해 선형적으로 저장하지 않고, Tree 형태로 저장하여 검색 속도의 향상을 추구한다.

작동원리 트라이는 주어진 문자열을 이루고 있는 문자를 앞에서부터 하나씩 노드를 생성해가며 만들어진다. 문자열을 트라이로 생성하는 과정 1.

주어진 문자열에서 현재 문자를 가져온다. 2. 현재 문자로 이루어진 노드가 존재한다면, 해당 노드로 그 다음 문자열을 탐색하고, 없다면 그 노드를 새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다. 3.

문자열의 마지막이 될 때까지 위의 과정을 반복한다. 예시) [ A..........