[Algorithm] Trie(트라이) 알고리즘

트라이 알고리즘은 트리를 이용한 문자열 검색 알고리즘으로 부분문자열 중복이 많이 일어나는 경우 적합한 알고리즘이다.

단, 메모리가 크다는 단점이 존재하다.

 

1. 트라이 구조

 

위와 같이 트라이는 문자열 하나하나가 노드가 되며 노드들을 타고 leaf로 가면서 하나의 문자열을 완성하는 트리 알고리즘이다.

트라이 노드들은 bool값을 하나씩가지는데 이는 문자열의 끝인지 아닌지를 나타내는 변수이다.

 

위 트리노드는 아래 배열로써 아래 5가지 문자열로 구성된 트라이 트리이다.

str = {ac, ab, aa, abee, bsea}

위에서 주황색 Node가 bool값이 true즉 문자열의 끝을 의미한다고 할 수 있다.

1) insert

Insert는 매우 간단하다 child를 따라가면서 문자열의 끝까지 넣어주고 마지막에 bool값을 true로 바꿔주면된다.

 

2) find

find역시 child를 따라가면서 마지막으로 도착한 노드가 bool값이 true를 가지면 된다. 만약 false이거나 중간에 길이 끊긴다면 존재하지 않는 문자열임을 알 수 있다.

 

트라이 알고리즘은 위처럼 트리를 이용해서 빠르게 찾아갈 수 있고 부분문자열 중복이 심한경우 유리하나 child를 모두 알파벳 혹은 알파벳+숫자등 문자열의 개수만큼 가져야 하기 때문에 메모리적으로 매우 낭비가 큰 알고리즘이다.