트라이 자료구조

트라이(Trie)란?

트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.

우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어 있는 자료구조입니다.

Trie라는 말은 탐색 트리(retrieval tree)에서 나온 단어입니다.

https://twpower.github.io/187-trie-concept-and-basic-problem

트라이 자료구조의 예시이며 주황색으로 된 노드들이 입력된 문자열입니다.

예를 들어 cat이라는 단어를 검색하기 위해서는 제일 먼저 'c'를 찾고, 다음에 ca 그다음에 cat의 순서로 찾습니다.

 

여기에서는 리프노드(끝 노드)들에 모든 문자열들이 들어가 있습니다. 

 

트라이 자료구조의 장단점

문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색하는 것보다 시간 복잡도에서 훨씬 더 효율적입니다.

각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점이 있습니다.

 

예제를 통한 트라이 자료구조의 이해

'abc', 'ab, 'car' 단어들을 'abc부터 트라이 자료구조에 저장해 보겠습니다.

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

1. 'abc' 트라이 자료구조에 삽입

• 첫 번째 문자는 'a입니다. 초기에 트라이 자료구조는 비어있기 때문에 Head의 자식 노드에 'a'를 추가해줍니다.
• 'a'노드에도 현재 자식이 하나도 없기 때문에 'a의 자식노드에 'b'를 추가해 줍니다.
• 'c'도 마찬가지로 'b'의 자식노드로 추가해줍니다.
• 'abc'단어가 끝남을 알리기 위해 현재 노드에 abc라고 표시합니다. (Data)

다음은 ABC 삽입의 예시입니다.

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

 

2. 'ab' 트라이 자료구조에 삽입

• 현재 Head의 자식노드에 'a가 존재합니다. 따라서 'a'를 추가하지 않고 기존에 있는 'a'노드로 이동합니다.
• 현재 'b'도 'a'의 자식노드로 이미 존재합니다.'b'노드로 이동합니다.
• 'ab' 단어가 여기서 끝이므로 현재 노드에 ab를 표시합니다.

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

3. 'car' 트라이 자료구조에 삽입

• Head의 자식노드로 'c'는 존재하지 않습니다. 따라서 'c'를 자식 노드로 추가합니다.
• 'c'의 자식노드가 없으므로 'a'를 추가합니다.
• 'a'의 자식노드가 없으므로 'r'를 추가합니다.
• 'car' 단어가 여기서 끝나기 때문에 현재 노드의 Data에 car를 기록합니다.

 

 

출처

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)

https://the-dev.tistory.com/2

[자료구조] Trie(트라이)-1 : 기초 개념