# Trie

> `Trie` 는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

<figure><img src="https://2913512558-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F2HjC6nD3GkaPFBpY46x0%2Fuploads%2FKBnsgLuXu2yR2hTWcK27%2Fimage.png?alt=media&#x26;token=f07b7bc9-cb0c-4831-a29f-2af4e00e0928" alt=""><figcaption></figcaption></figure>

* `Trie` 는 루트 노드에서부터 자식 노드로 내려가면서 문자열이 저장된다.
* `Trie` 를 이용하여 문자열을 빠르게 탐색할 수 있다.
  * 모든 문자열을 비교하는 것이 아니라, 탐색할 문자열을 한 문자씩 루트 노드부터 내려가면서 탐색한다.
  * 저장 공간의 크기가 커진다는 단점이 있다.
* 접두사가 같은 문자열은 같은 노드를 공유한다.
* 단어의 끝을 나타내는 변수를 이용하여 구분할 수 있다.

#### 삽입

* 루트 노드부터 삽입할 문자열의 한 문자씩 탐색하면서 내려간다. 존재하지 않으면, 노드를 추가하고 계속 내려간다.
* 문자열의 마지막 문자는 마지막 노드를 표시한다.

#### 탐색

* 루트 노드부터 문자열의 한 글자씩 탐색한다.
* 탐색 과정 중 노드가 존재하지 않거나 마지막 글자 노드에서 마지막 노드 표시가 없다면, 존재하지 않는 문자열이다.

#### 삭제

* 문자열의 마지막 노드로 가서 마지막 노드 표시를 없애준다.
* 마지막 노드에서부터 올라가면서 다른 자식 노드가 없다면 해당 노드를 삭제하면서 올라간다.
