Trie

  • Trie란 prefix tree라고도 불림
  • 문자열을 한 문자 단위로 분해하여 tree를 만들어 검색을 빠르게 만들어 주는 자료구조
  • 문자열을 다루는 경우 많이 사용
  • 문자열의 길이가 M인 문자열이 N개가 있고 정렬되어 있을 때, 특정 문자열이 N개의 set에 포함 되는지 아닌지 알아 보는 문제.  이 경우 보통 이진탐색을 떠올리는데 이는 시간복잡도가 O(MlgN)이다. 하지만 Trie를 사용하면 O(M)의 시간복잡도로 검색
  • 구조 참조 : https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4
    • 루트는 빈 노드
    • 부모 노드에 접미 문자 하나씩을 붙여서 자식 노드를 생성
    • 간선은 접미 문자가 붙는 것을 나타냄
    • 종료노드 표시가 필요. basement의 경우 base에서 끝날 수도, basement에서 끝날 수도
  • Trie 사용해야하는 이유 : 문자열은 정수 실수와 달리 그 길이가 변하기 때문에 검색에 시간이 많이 걸림. 정수 실수의 경우 O(lgN)에 가능한데 문자열은 O(MlgN)이 필요. 많은 문자열을 다루는 문제에서는 거의 Trie를 사용해야만 제한된 시간 안에 정답이 나옴

 

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat