Tree Structure 노트9 - Trie

탐색 트리 트라이

문자열 탐색을 위한 Trie(Prefix tree) 

 

내용이 있다는 것과 그것이 '인식될 수 있는 형식'으로 표현된 것은 다르다.

주소 시스템 같이 내용이 많은걸 할때 씀. 휴대 전화에서 쓰이는 것 같은 예측 문자나 자동 완성에 필요한 사전을 저장하는 것들도 일반적인 응용중 하나/ 주로 문자열이 key인 경우가 많음./ 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다.

 

Trie의 장단점 :

ㆍ트라이는 문자열 검색이 빠름.

ㆍ문자열 탐색시, 하나하나 모두 비교하면서 탐색을 하는 것 보다 시간 복잡도 측면에서 훨씬 효율적임.

ㆍ각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음.

 

구현 :

key에는 해당 노드의 문자가 들어가고, child에는 자식노드가 포함되게 한다. / data는 문자열이 끝나는 위치를 알려주는 역할을 한다. / 해당 노드에서 끝나는 문자열이 없을 때는 None으로 내버려둔다.

 

가장 긴 문자열의 길이가 L이고 총 문자열들의 수가 M일 때, Trie의 생성 시간 복잡도는 O(M*L), 탐색 시간 복잡도는 O(L).

 

Trie에서 문자열 탐색 : 'abc'문자열이 있는가를 탐색한다 할때

- Head의 child에 'a'가 존재 --> 'a노드' (key 'a')로 이동. / 'a'노드의 child에 'b'가 존재 -->  'b노드' (key 'b')로 이동 /  'b'노드의 child에 'c'가 존재 -->  'c노드' (key 'c')로 이동 / 문자열 탐색 완료. 현재 노드 'c'에 Data가 존재하면 문자열이 존재하는 것.

 

 c

  |

 o

  |

 m

  |

 p

  |

 u 

  |

  t

|   |

e  i

|   |

r  n

    |

   g

 

Radix Tree(Compact Trie) (짜부러트린 트라이)

여기서 radix는 node가 가질 수 있는 최대 자식의 갯수이다(서로 구분되는 문자의 총 갯수). trie도 radix와 같은 의미를 갖지만 radix tree는 trie 중에서 특별히 compact tree를 지칭함.

 

radix trie의 전체 노드 갯수가 O(N)이 되는 것의 증명 : root의 child인 경우 -> 전체 key에 해당하는 하나의 노드만 생김. / 그 외, branch 노드가 없을때, branch 노드 및 그 이하 뒷부분에 해당하는 노드 2개가 생김. branch 노드가 있으면, 그 이하 뒷부분에 해당하는 노드 1개가 생김. / 매 key 추가시 1 또는 2의 상수개 노드만 생기므로 전체 N개의 key에 대해 O(N)의 노드 개수를 가짐.

 

 

comput

/       |

er     ing