[자료 구조] 트라이(Trie)

🤔 트라이란?

=> 주로 문자열을 검색하거나 저장된 문자열과 특정 문자열이 일치하는지 판별하는 데 쓰이는 특수한 트리이다.

 

⇒ 위 그림은 Sammie, Simran, Sia, Sam이라는 문자열을 저장한 트리이다. 각 노드는 분기되어 완전한 단어를 이룬다. 또한 각 노드는 경로의 끝을 나타내는 isCompleted이라는 boolean flag를 갖는다. 예를 들어 Sam이라는 문자열의 m은 endOfWord를 true로 만들어 해당 문자열의 끝임을 나타낸다.

---

노드 생성

⇒ 트라이 노드는 자식을 저장하는 중첩된 객체를 사용하여 형성된다. 각 객체는 자신의 자식을 키로 삼는다. Trie 클래스는 위에서 보듯 TrieNode 클래스의 생성자에 의해 발현되는 root 노드를 갖는다.

---

삽입

⇒ 문자열을 트라이에 저장할 때 자식 노드가 존재하지 않는다면 root에 생성된다. 단어의 각 문자가 저장되고, 각 문자가 자식 노드로 존재하지 않는다면 문자별 자식 노드가 생성된다.

---

검색

⇒ 트라이에서 문자열을 찾으려면 문자열의 각 문자를 확인해야 한다. 이는 current라는 임시 변수를 root에 설정하여 수행된다. current는 문자열의 각 문자가 확인될 때마다 갱신된다.

---

삭제

⇒ 삭제 기능을 구현하려면 문자열의 끝 문자에 이를 때까지 root 노드를 탐색해야 한다. 각 노드가 더 이상 어떠한 자식도 가지지 않는다면 삭제를 수행한다. 예를 들어 sim을 삭제한다고 하면 s는 건들지 않고 i, m을 삭제한다. 이러한 작업을 재귀적으로 구현하는 것이다.