트라이 (Trie) 자료구조는 문자열을 저장하고 효율적으로 탐색하기 위한 트리(Tree) 형태의 자료구조의 특별한 형태이다.

• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열 탐색하는데 특화된 자료구조라고 할 수 있다.
• 래딕스 트리(Radix Tree) or 접두사 트리(Prefix Tree) or 탐색 트리(Retrieval Tree)라고도 한다. 트라이는 Retrieval Tree에서 나온 단어이다.
• 예를 들어 ‘Trie’ 라는 명칭의 단어를 검색하기 위해서는 루트노드(Root Node)에서 제일 먼저 ‘T’를 찾고 다음 ‘r’,….’e’순으로 찾으면 된다. 이러한 개념을 적용한 자료구조이다.

장점

• 문자열 검색을 빠르게 한다.
• 문자열을 탐색할때 하나 하나식 무차별탐색(Brute Force)하는 것보다 시간복잡도 측면에서 훨씬 더 효율적이다.

단점

• 각 노드에서 자식들에 대한 포인터들을 모두 배열로 저장 한다는 점에서 메모리측면에서 비효율적일 수 있다

( 위 그림으로 보면 t, A, i 처럼 루트노드에서 갈 수 있는 것들을 다 기록하고 있어야 한다. )

예시

‘abc’, ‘ab’, ‘car’ 단어들을 ‘abc’부터 트라이(Trie)에 기록한다고 했을때는 가정하면 아래와 같다.

1. ‘abc’를 트라이(Trie)에 삽입

   

   • 먼저 트라이의 루트노드를 생성 한다음 그 루트노드에 자식을 ‘abc’ 배열의 첫번째 값인 ‘a’를 자식으로 추가해준다.
   • 자식인 ‘a’노드는 방금 생성된 노드이므로, 자식들이 아무것도 없다. ‘a’노드에 ‘abc’ 배열의 다음 값인 ‘b’를 자식으로 추가 해준다.
   • ‘abc’배열의 마지막값인 ‘c’도 b의 자식노드에 추가해준다.
   • ‘abc’배열의 값을 모두 트라이에 넣어줬으므로 현재 노드 c에 단어가 존재한다고 기록하고 abc를 기록한다.

2. ‘ab’를 트라이(Trie)에 삽입

   

• 현재 Root에 ‘abc’를 넣을때 생성했던 ‘a’노드가 이미 존재 하므로 a로 이동한다.