[Data Structure] Trie란? (feat. 이론)

안녕하세요 Foma 💻 입니다!

 

오늘은 연결된 문자열을 효율적으로 저장해 검색을 효율적으로 도와주는 자료구조인 트라이(Trie)에 대해 정리해 보려고 합니다!

 

바로 시작할게요~

---

Trie란?

 

트라이(trie)는 컴퓨터 과학에서 탐색 트리의 일종이다. 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. - 위키 백과 -

 

즉, 트리 형태로 연결된 문자열을 차례로 저장하는 자료구조 입니다.

 

이름의 유래는 트리 형태로 되어있기 때문에 트리라고 불리다가 실제 트리 자료구조와 이름이 헷갈려서 트라이라고 불리게 되었다고 하네요.

 

아래 그림을 보면 이해가 쉬울 것 같습니다.

 

 

---

Example

 

1. 검색

 

일상 생활 속의 예제로는 아래와 같이 문자열을 검색할 때 효율적으로 사용할 수 있습니다.

 

검색한 단어 뒤 노드에 어떤 글자들이 있는지 쉽게 검색할 수 있기 때문에 아래와 같이 그 뒤로 이어지는 단어 혹은 문자열이 뜨는 것이죠.

 

 

2. 스펠링 체크

 

사전 속의 모든 단어들을 트라이 자료구조로 저장해 놓았다면 해당 단어가 사전 속에 있는지 없는지 빠르게 탐색할 수 있습니다.

 

아래와 같이 사전 속에 있지 않은 단어라면 스펠링이 틀린 게 아닌지 빠르게 알려줄 수 있는 것이죠.

 

 

---

 

 

Search

 

만약 단어가 "Face", "Fat", "Farm", "From" 이렇게 있다면 트라이엔 어떻게 저장될까요?

 

아래와 같이 저장될 것 입니다.

 

 

만약 우리가 찾고 싶은 단어가 "Fame" 이라면 어떻게 검색해야 할까요?

 

먼저 가장 첫 번째 레벨을 살펴봐야겠죠? F가 있으므로 F의 자식들을 탐색합니다.

 

 

 

두 번째 레벨인 "A"와 "R"을 탐색한 결과 'Fame'의 두 번째 글자인 "A"가 있죠? A의 자식들을 탐색합니다.

 

 

세 번째 레벨엔 'Fame'의 세 번째 글자이 m이 존재하지 않습니다.

 

고로 'Fame'은 현재 트라이에 존재하지 않는 단어라고 할 수 있습니다.

 

 

---

Insert

 

위와 같이 단어가 존재하지 않을 경우에 트라이에 추가해 줘야겠죠?

 

위와 같이 자식들을 살펴 보았는데 해당 글자가 없는 경우 자식들에 추가해 줍니다.

 

 

 

그 다음 'M'의 자식으로 'Fame'의 다음 글자인 'E'를 추가해 줍니다.

---

Complexity

 

시간 복잡도는 단어의 갯수가 n, 단어의 평균 길이가 l이라고 가정했을 때 삽입은 O(n*l)이 됩니다.

 

아무리 긴 문장이 있더라도 원하는 한 단어를 찾는데 O(n)만 걸리기 때문에 시간적인 측면에서 효율적인 자료구조라고 볼 수 있습니다.

 

공간 복잡도는 허용되는 글자의 갯수 n, (ex: alphabet 26글자, 한글 24글자)

 

단어의 평균 길이 l, 각 자식들의 평균 갯수 t 라고 하면 O(n*l*t)가 됩니다.

 

고로 공간적인 측면에서는 비효율적인 자료구조라고 볼 수 있습니다.