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

 

안녕하세요. 개발개입니다.

 

이번 글에서는 Trie의 기초 개념에 대해 설명합니다.
어려운 내용보다는 기본적인 개념에 주안점을 두고 작성했습니다.

 

오타, 오류 혹은 기타 의견은 언제든지 환영합니다.

 

 You can also read this post in English via the link below : 
[EN/DATA STRUCTURE] - [DataStructure] Trie-1 : The Basis of The Trie Data Structure

 

 

 

 

---

 

 

Trie 자료구조란?

일반 트리 자료구조 중 하나로, Digtal Tree, Radix Tree, Prefix Tree라고도 불립니다.
텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조입니다.

* 발음 : 트라이 
  - 처음엔 '트리'였지만, 트리(Tree) 자료구조와 구분하기 위해 '트라이'로 바뀌었다.

그림1. 트리 자료구조의 종류

 

 

 

Trie 자료구조의 형태는?

각 노드는 <Key, Value> 맵을 가지고 있습니다. 여기서 Key는 하나의 알파벳이 되고,  Value는 그 Key에 해당하는 자식노드가 됩니다.

다음 그림은 DEV, DEAR, PIE, POP, POW라는 단어가 들어있는 Trie 자료구조를 도식화한 것입니다.
휴대폰 전화번호부에서 검색을 하거나 사전에서 단어를 찾는 것과 같습니다.
예를 들어, 아래 그림에서 'DEV'라는 문자열을 찾으려면, 루트 노드에서부터 순차적으로 [D] → [E] → [V] 탐색합니다.

 

그림2-1. Trie 자료구조 도식화

 

그림에서 볼 수 있듯이 루트 노드는 특정 문자를 의미하지 않고 자식 노드만 가지고 있습니다.
유의할 점은 노드들이 '부모 노드'나 '자신이 어떤 알파벳(Key)에 해당하는 노드(Value)인지'를 가지고 있는게 아니라는 점입니다.

즉, 루트노드는 [D], [P]라고 하는 알파벳을 Key로 하는 자식 노드들을 가지고 있고,
[D]는 [E]를 Key로 하는 자식노드, [P]는 [I]와 [O]를 Key로 하는 자식노드들을 가지고 있는 것입니다.

또 루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다는 특징이 있습니다.
즉, 'DE' 노드의 자손인 'DEAR'와 'DEV'는 'DE-'를 공통 접두어로 가지며, 'P' 노드의 자손인 'POW'와 'PIE'는 'P-'를 공통 접두어로 가집니다.

 

그림2-2. Trie 자료구조의 공통 접두어

 

 

---

 

Trie 자료구조의 특징을 정리하면,

• 정렬된 트리 구조이다.
  (데이터에 따라 이진트리일 때도 있다)
• Trie는 자식노드를 맵<key, value> 형태로 가지고 있다.
  
• 루트를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다.
• 루트 노드는 빈 문자와 연관 있다.
  (특정 문자가 할당되어있지 않다)

 

---

 

다음 글에서는 JAVA로 Trie를 구현해봅니다.

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

 

 

---

 

 

본 글은 다음을 참고하여 작성되었습니다.

 

- 개념 설명
https://en.wikipedia.org/wiki/Trie

Trie - Wikipedia

https://brunch.co.kr/@springboot/75

트라이(Trie) 자료구조