[Trie] 문자열 검색이 용이하게 만든 트리

안녕하세요 Dibrary입니다.

Trie 자료구조는 트리 형태의 자료구조인데, '문자열' 검색을 용이하게 하기 위한 자료구조 입니다.

 

먼저 구글에 Trie python를 검색해보면 여러 이미지들이 나옵니다.

그 중에 한 개를 살펴 보죠.

이게 뭘 의미하는거냐면, to와 tea와 ten이라는 단어는 똑같이 t로 시작하죠? 그래서 t라는 노드 밑에 위치합니다.

to에서 o는 tea와 ten에 없으므로 t 노드 밑에 o가 있음으로써, 해당 경로로 검색을 하게 되면 to가 나오는 것이죠.

tea와 ten은 t도 똑같고, e도 똑같습니다. 따라서 t노드 밑에 e노드가 있고,  e노드 밑에 a와 n으로 나뉘는 것이죠.

이런식으로 문자열을 저장해두고, 찾을 때는 금방 찾게 만든 자료구조가 Trie 입니다.

 

---

파이썬으로 코드를 구현 해 보면 아래와 같습니다.

핵심 코드는 insert의 for문 부분 입니다.

word로 들어온 문자열을 char로 한단어씩 잘라서 node.children에 설정하고, 해당 노드를 다시 node로 설정해서 children의 children으로 단어들을 넣어나가는 것이죠.

 

과연 위에서 말한대로 나올지 확인해보겠습니다.

 

먼저 apple이라는 단어를 넣었습니다. root의 children에는 apple의 첫 단어인 a가 있겠네요. 

그리고 b로 시작하는 단어인 banana도 넣었습니다. 다시 root의 children에는 b가 추가로 들어간 것을 볼 수 있습니다.

startsWith의 결과를 보면 b로 시작하는 단어도 있다고 나옵니다.

 

그럼 apple과 alpha 2개를 넣은 a의 트리를 살펴보겠습니다.

root의 a노드로 들어가보니 p와 l이 있다고 나옵니다. 단어 2개를 넣었고, ap, al로 시작하니까 a 밑에 p와 l이 있는게 맞습니다.

apple을 살펴보고자, a노드 밑의 p노드를 살펴보니 children으로 p가 있다고 나오고, 해당 노드 밑에는 l이, 그 노드 밑에 e가 있다고 나옵니다.

합해보면 apple이 맞는 것을 볼 수 있습니다.