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

문자열

 

[자료구조 소개]

문자열을 char단위로 쪼개서 트리에 저장한 자료구조. 문자열 검색에 용이함.

 

---

[자료구조 특징]

• 트리 사용.
• 재귀, 포인터(C++ 사용 시), 트리에 대한 지식 필요
• 공간, 시간 복잡도를 효율적으로 개선함
  (기존의 방식으로 문자열을 찾으려면 문자열 길이 M, 배열 길이 N으로 복잡도가 $O(NM)$, 트라이는 $O(M)$)

---

[코딩 방법]

1. 클래스(구조체) 생성, 현재 노드가 끝인지(문자열이 끝인지) 확인하는 bool타입 변수와 자식노드를 가리킬 객체포인터배열(C++) 혹은 객체배열(Java) 생성. 
2. 객체포인터배열은 nullptr(C++) 혹은 null(Java)로 초기화. C++의 경우 동적할당을 사용하므로 자식노드를 삭제할 소멸자도 생성. (!if (child[i]) delete child[i])
3. main에서 root생성. (동적할당도, 일반 객체도 가능)
4. 문제에서 요구하는대로 이런저런 메소드들을 구현하면 됨.
   예시를 들자면 insert의 경우 for문을 돌려가면서 Trie* cur = this로 시작했다가 cur을 계속 child로 갱신하고 이어붙일 수 있고,
   pop의 경우 재귀를 돌려가면서 요소를 삭제하고 nullptr로 초기화해주다가 다른 갈래가 있으면 삭제를 중단하면 됨.
   메소드를 구현할 때 child들을 nullptr(null)로 초기화하는 것을 잘 이용할 것.

---

[시간 복잡도]

최대 문자열 길이가 M이면 $O(M)$

 

---

[공부용 링크]

https://www.youtube.com/watch?v=TohdsR58i3Q 

※ 1분 45초 만에 트라이 이해 가능