Trie

Trie

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

• 트라이를 구성하는 각 노드는 하나의 문자(Character)를 표현하며, 문자열 전체는 루트에서 리프까지의 경로로 표현되기 때문에, 특정 문자열 또는 접두사를 찾는 연산이 매우 직관적이고 빠릅니다.
• 각 노드의 자식 노드는 보통 고정 크기 배열(알파벳 수) 또는 해시맵(동적)으로 표현됩니다.

루트에서 특정 노드까지의 경로가 문자열의 접두사(Prefix)를 그대로 나타내므로 Prefix Tree라고도 불립니다.

Operation

트라이에는 크게 4가지 연산이 있습니다. 각 연산 과정을 알아보도록 하겠습니다.

1. 삽입 (Insert)
2. 탐색 (Search)
3. 삭제 (Erase)
4. 접두사 확인 (StartsWith)

Insert

Insert는 트라이에 문자열을 삽입하는 연산입니다. 각 문자를 따라 노드를 만들며, 마지막 문자에서 종료 표시(terminal)를 남깁니다.

가장 먼저 STRING 문자열을 트라이에 삽입하는 과정을 보겠습니다.

1. S: 루트 노드의 자식에 자식 노드가 한개도 없습니다. 따라서 문자 S에 해당하는 노드를 생성하여 루트 노드의 자식으로 추가하고 해당 노드로 이동합니다.
2. T: S 노드의 자식 중에 T 노드는 없습니다. 따라서 T 노드를 생성하고 S의 자식으로 추가하고 해당 노드로 이동합니다.
3. R: T 노드의 자식 중에 R 노드는 없습니다. 따라서 R 노드를 생성하고 T의 자식으로 추가하고 해당 노드로 이동합니다.
4. I: R 노드의 자식 중에 I 노드는 없습니다. 따라서 I 노드를 생성하고 R의 자식으로 추가하고 해당 노드로 이동합니다.
5. N: I 노드의 자식 중에 N 노드는 없습니다. 따라서 N 노드를 생성하고 I의 자식으로 추가하고 해당 노드로 이동합니다.
6. G: N 노드의 자식 중에 G 노드는 없습니다. 따라서 G 노드를 생성하고 N의 자식으로 추가합니다.
   • 마지막 문자이므로, 해당 노드에 terminal = True로 표시합니다.

STRIP 문자열을 트라이에 삽입하겠습니다.

1. S: 루트 노드의 자식 중에 S 노드가 이미 존재하므로 해당 노드로 이동합니다.
2. T: S 노드의 자식 중에 T 노드가 이미 존재하므로 해당 노드로 이동합니다.
3. R: T 노드의 자식 중에 R 노드가 이미 존재하므로 해당 노드로 이동합니다.
4. I: R 노드의 자식 중에 I 노드가 이미 존재하므로 해당 노드로 이동합니다.
5. P: I 노드의 자식 중에 P 노드가 존재하지 않으므로 새로 생성하여 추가합니다.
   • 마지막 문자이므로 terminal = True로 표시합니다.

EVERY 문자열을 트라이에 삽입하겠습니다.

1. E : 루트 노드의 자식 중에 E 노드가 존재하지 않으므로 새로 생성하여 추가합니다.
2. V : E 노드의 자식 중에 V 노드가 존재하지 않으므로 새로 생성하여 추가합니다.
3. E : V 노드의 자식 중에 E 노드가 존재하지 않으므로 새로 생성하여 추가합니다.
4. R : E 노드의 자식 중에 R 노드가 존재하지 않으므로 새로 생성하여 추가합니다.
5. Y : R 노드의 자식 중에 Y 노드가 존재하지 않으므로 새로 생성하여 추가합니다.
   • 마지막 문자이므로 해당 노드에 terminal = True로 표시합니다.

마지막 문자열 EVE 문자열을 트라이에 삽입하겠습니다.

1. E : 루트 노드의 자식 중에 E 노드가 이미 존재하므로 해당 노드로 이동합니다.
2. V : E 노드의 자식 중에 V 노드가 이미 존재하므로 해당 노드로 이동합니다.
3. E : V 노드의 자식 중에 E 노드는 존재하지 않으므로 새로 생성하여 추가합니다.
   • 마지막 문자이므로 해당 노드에 is_terminal = True로 표시합니다.

Search

Serach는 트라이에 해당 문자열이 존재하는지 확인하는 연산입니다. 각 문자를 따라 내려가며, 마지막 문자가 종료 노드인지 검사합니다.

EVE 문자열이 트라이에 존재하는지 확인해보겠습니다.

1. E : 루트 노드의 자식 중에 E 노드가 존재하므로 해당 노드로 이동합니다.
2. V : E 노드의 자식 중에 V 노드가 존재하므로 해당 노드로 이동합니다.
3. E : V 노드의 자식 중에 E 노드가 존재하므로 해당 노드로 이동합니다.
   • 해당 노드는 terminal = True로 설정되어 있으므로, "EVE"는 트라이에 존재합니다.

Erase

StartsWith

Implementation

Reference