#12 트리(Tree) 6 - 트라이(Trie)

1. 트라이(Trie)

 트라이(Trie)는 문자열의 빠른 탐색을 위해 고안된 트리이다. 하나의 노드가 하나의 문자를 나타내도록 하여

문자열을 저장해나가는 것으로 검색할 문자열의 길이가 N 일 때, O(N)의 복잡도로 탐색을 마칠 수 있다.

하나의 문자열의 끝임을 표시하기 위해 문자열의 마지막 문자인 노드를 식별할 수 있도록 한다.

위 그림의 트라이는 문자열의 마지막 문자인 노드를 주황색으로 표시한 것이다.  위 트라이에 저장된 문자열은

be, bee, bean, app, apple, apart 의 6개가 된다.

 

 

2. 특징

• 길의 N의 문자열을 삽입할 경우 O(N)의 시간복잡도로 삽입 가능
  
  
• 길이 N의 문자열을 탐색할 경우 O(N)의 시간복잡도로 탐색 가능
  
  
• 저장된 문자열 중 지금까지 입력한 문자열로 시작하는 모든 문자열을 파악할 수 있기 때문에 
  자동완성 기능의 구현에 사용됨

트라이의 삽입/탐색 연산은 굉장히 간단하기 때문에 구현 파트에서 주석으로 간단히 설명하고 넘어가기로 한다.