트라이(Trie)

Trie는 문자열을 저장하고, 효유적으로 탐색하기 위한 트리 형태의 자료구조이다. 여기서 trie라는 이름은 retrieval tree에서 나온 단어이다. 즉, Trie는 radix tree, prefix tree, retrieval tree라고도 한다.

 

Trie의 핵심 개념은 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라는 것이다. 예를들어, Datastructure라는 단어를 검색하기 위해서 제일 먼저 D를 찾고, 그 다음에 a, t .. 순서로 찾는 이러한 개념을 적용한 것이 Trie이다.

 

그렇다면 트라이의 장점은 무엇일까?

트라이의 장점은 문자열 검색을 빠르게 한다는 것이다. 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다.

 

하지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. 즉, 메모리 공간 측면에서 보면 비효율적 일수도 있다는 것이다.

 

예제를 통한 트라이 이해

'abc', 'ab', 'car' 라는 단어들을 'abc'부터 트라이에 저장한다고 가정해보자.

우선 'abc'를 트라이에 삽입하는데, 첫 번째 문자 'a'를 삽입하려고 하는데 트라이 자료구조 내에는 아무것도 없으므로 Head의 자식 노드에 'a'를 추가해주고, 'a'노드에도 현재 자식이 하나도 없으므로 'b', 'c'를 삽입해준다. 그리고 'abc'단어가 여기서 끝남을 알리기 위해 현재 노드에 abc라고 표시한다.

그럼 이제 다음 단어인 'ab'를 삽입해보려하자. 근데 현재 Head의 자식노드로 'a'가 이미 존재한다. 따라서 기존에 있는 'a'노드로 이동한다. 'ab' 단어가 여기서 끝나므로 현재 노드에 ab를 표시한다.

마지막으로 'car'단어를 삽입해보자. Head의 자식 노드로 'a'만 존재하고, 'c'는 존재하지 않으므로 'c'를 자식노드로 추가한다. 그리고 'c'의 자식노드가 없으므로 'a'를 추가하고, 'a'의 자식노드가 없으므로 'r'을 추가한다. 'car' 단어가 여기서 끝이므로 현재 노드에 car를 표시한다.

 

트라이의 시간 복잡도

트라이의 시간 복잡도는 제일 긴 문자열의 길이를 L이라고 하고, 총 문자열들의 수를 M이라고 할 때, 생성 시간 복잡도는 모든 문자열 M개를 넣어야하고, M개에 대해서 트라이에 넣는건 가장 긴 문자열 길이인 L만큼 걸리므로 O(ML)이다. 또한 삽입 시간 복잡도는 가장 긴 문자열 길이로 O(L)이 나온다. 마지막으로 탐색 시간 복잡도는 트리를 제일 깊게 탐색하는 경우로 가장 긴 문자열 길이인 L까지 깊게 들어가는 것이므로 O(L)의 시간 복잡도가 나온다.

 

트라이에서 문자열 탐색

트라이에서 문자열 탐색을 하려면 각 문자의 노드의 child 값을 따라가서 최종적으로 Data 값이 존재하는지 보면된다.

즉, 다음과 같은 흐름을 따라가면 된다.

위의 트라이에 'abc' 문자열이 있는지 탐색해보자.

• Head의 child에 'a'가 존재 --> 'a'노드(key='a')로 이동
• 'a'노드의 child에 'b'가 존재 --> 'b'노드(key='b')로 이동
• 'b'노드의 child에 'c'가 존재 --> 'c'노드(key='c')로 이동
• 문자열 탐색이 완료됨 --> 현재 노드('c'노드)에 Data값이 존재! --> 따라서 'abc'라는 문자열이 존재함을 알 수 있음

'ca'라는 문자열이 있는지 탐색해보자.

• Head의 child에 'c'가 존재 --> 'c'노드(key='c')로 이동
• 'c'노드의 child에 'a'가 존재 --> 'a'노드(key='a')로 이동
• 문자열 탐색이 완료됨 --> 현재 노드('a'노드)에 Data값이 없음! --> 따라서 'ca'라는 문자열은 존재 X

 

인용

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie

[자료구조] 트라이 (Trie)