트라이 (Trie)

트라이 (Trie) ?

도입

• 정수나 실수형 변수는 크기가 항상 정해져 있기 때문에 비교하는데 있어서 상수 시간이 걸린다고 가정해도 된다.
• 하지만 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문에 다르게 다뤄야 한다.
• N개의 원소를 갖는 이진 탐색 트리에서 원하는 원소를 찾는 경우, 원소 간의 비교를 상수 시간에 할 수 있을 때는 시간 복잡도가 O(log N) 라고 할 수 있다.
• 하지만, 문자열의 비교에는 길이에 비례하는 시간이 걸리므로 문자열의 최대 길이 M을 곱한 O(M * log N) 의 시간 복잡도가 된다.
• 이러한 문제들을 해결하기 위해 고안된 자료구조가 트라이이다.

소개

• 트라이는 문자열의 집합을 표현하는 트리 자료구조이며, Prefix Tree 또는 Digital Tree라고도 불린다.
• 문자열을 굉장히 빠르게 탐색하며, 명칭의 유래는 Retrieval (탐색) 이라는 단어에서 나왔다.
• 집합 내에서 원하는 원소를 찾는 작업에 대해 O(M) 의 시간복잡도가 된다.

• 위 그림은 문자열 집합 S = {"BE", "BET", "BUS", "TEA", "TEN"} 을 저장하는 트라이의 예이다.
• 그림에서 볼 수 있듯이 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다.
• 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다.
• 트라이의 루트는 항상 길이 0인 문자열에 대응되며, 노드가 깊어질 때마다 대응되는 문자열의 길이는 1씩 늘어난다.
• 그림에서 짙은 회색으로 표시된 노드들은 종료 노드들로, 이 노드들은 해당 위치에 대응되는 문자열이 집합에 포함되어 있다는 것을 나타낸다.

 

• 트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있으며, 따라서 각 노드에는 대응되는 문자열을 저장할 필요가 없다.
• 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과 이 노드가 종료 노드인지를 나타내는 불린 값 변수로 구성된다.
• 이때 자손 노드들을 가리키는 포인터 목록은 동적 배열이 아닌, 입력에 등장할 수 있는 모든 문자에 각각 대응되는 원소를 갖는 고정 길이 배열로 구현된다.
• 예를 들어, 알파벳 대문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 26개짜리 포인터 배열을 가지고 있으며, 이 배열의 0번 원소는 대응되는 문자열의 맨 뒤에 글자 A를 붙일 경우 얻을 수 있는 문자열 노드의 포인터를 나타낼 것이다.
• 만약 해당 노드가 없다면 NULL을 저장하면 된다. 이와 같은 구조는 트라이의 최대 문제로 언급되는 메모리를 엄청나게 낭비한다는 것이지만 다음 노드를 찾는 과정에서 어떤 탐색도 필요하지 않다는 장점을 가져다 준다.

 

Code

TrieNode 클래스

• 트리를 이루는 각 노드 객체를 만드는 클래스이다.
• 알파벳은 총 26개가 있으므로 각 노드마다 26개의 자식 노드를 가질 수 있도록 배열을 만들어준다.
• isEndofWord는 노드가 터미널 노드인지 (문자열 끝부분) 여부를 확인하는 boolean 변수이다.

Trie 클래스

• Trie 클래스에는 문자열 탐색을 할 때, root에서 출발하기때문에 클래스 변수로 root만 있으면 된다.

Insert 함수

• 문자열 (key) 이 입력되면 문자열을 확인하면서 root부터 차례대로 문자열 노드가 있는지 확인한다.
• 노드가 없다면 (null) 노드의 자식 노드에 추가한다. (new TrieNode()) 
• 이 과정을 문자열 끝까지 반복하고 isEndofWord 변수를 true로 만들어 끝부분이라는 것을 알려준다.

Search 함수

• Insert함수와 마찬가지로 문자열 길이만큼 비교하면서 노드가 없다면 (temp.children[idx] == null) 탐색하려는 노드가 없다는 것이므로 false를 반환한다.
• 마지막으로 노드가 비어있지 않으면서, 해당 노드가 마지막이라면 문자열을 찾은 것이므로 true를 반환한다.

• 위 코드를 가지고 예제를 돌려보면 다음과 같이 나온다.

Reference

• https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4
• https://jason9319.tistory.com/129
• http://clojure.or.kr/wiki/doku.php?id=study:algorithms:trie
• https://mjson.tistory.com/39
• https://www.geeksforgeeks.org/trie-insert-and-search/
• https://www.baeldung.com/trie-java