Trie

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

• Trie 는 루트 노드에서부터 자식 노드로 내려가면서 문자열이 저장된다.

• Trie 를 이용하여 문자열을 빠르게 탐색할 수 있다.

  • 모든 문자열을 비교하는 것이 아니라, 탐색할 문자열을 한 문자씩 루트 노드부터 내려가면서 탐색한다.

  • 저장 공간의 크기가 커진다는 단점이 있다.

• 접두사가 같은 문자열은 같은 노드를 공유한다.

• 단어의 끝을 나타내는 변수를 이용하여 구분할 수 있다.

삽입

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

• 문자열의 마지막 문자는 마지막 노드를 표시한다.

탐색

• 루트 노드부터 문자열의 한 글자씩 탐색한다.

• 탐색 과정 중 노드가 존재하지 않거나 마지막 글자 노드에서 마지막 노드 표시가 없다면, 존재하지 않는 문자열이다.

삭제

• 문자열의 마지막 노드로 가서 마지막 노드 표시를 없애준다.

• 마지막 노드에서부터 올라가면서 다른 자식 노드가 없다면 해당 노드를 삭제하면서 올라간다.