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

트라이

 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 혹은 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조. 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 주로 문자열이 키인 경우가 많고, 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 트라이는 트리와 유사하지만, 우리가 주로 살펴본 이진 트리의 모습이 아닌 전형적인 다진 트리(m-ary Tree)의 형태를 띤다.

 

트라이 자료구조 도식화

 도식을 참고하면, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. (이 부분은 어떻게 구현하냐의 차이인 것 같기도 함)

 

트라이 탐색 및 삽입의 시간 복잡도

1) 트라이 탐색

 트라이 탐색을 이용한다면, 문자열의 존재 여부를 파악할 때 문자열 길이만큼만 탐색하면 되기 때문에 빠른 시간 안에 문자열 탐색이 가능하다는 장점이 있다. 즉, 트라이 탐색의 시간 복잡도는 O(L)이다.

 

2) 트라이 삽입

 삽입 연산 또한 O(L)의 시간에 가능하다. 일단, 삽입을 위해서는 해당 문자열이 트라이 내에 존재하는지에 대해 탐색을 하는 작업이 선행되어야 한다. 이때, 문자열이 존재하지 않는지에 대해 판단하고, 나머지 요소를 삽입하는 데에는 역시 O(L)의 시간이 소요된다.

 

3) 트라이 삭제

 삭제 연산은 노드의 삭제가 아닌, 노드 값을 null로 변경하는 것으로 구현된다. 따라서 문자열을 삭제하기 위해서는 따로 노드 삭제에 따른 시간이 소요되지 않고 해당 노드의 값 변경만 있기 때문에, 역시 O(L)의 시간에 수행 가능하다. (근데 궁금한 점은 자식 노드가 존재할 수 있기 때문에 삭제를 안한다고 되어 있는데, null 값으로 변경하면 여전히 수행이 불가능하지 않나?)

 

4) 예시

 만약, APPLE이라는 단어가 트라이 내에 저장이 되어 있다면 APPLE의 요소를 하나하나 탐색하는 데에 문자열 길이인 5만큼의 시간이 소요된다.  또한 존재하지 않는다고 가정하더라도 APPLE을 삽입하는 데에는 여전히 문자열 길이인 5만큼의 시간이 소요가 된다. 문자열 APP만 저장이 되어 있고, APPLE은 저장이 되어 있는다고 하면, APP까지 탐색을 한 후 이후에 일치하는 문자열이 없다고 하면 LE에 대해서만 삽입하면 되기 때문이다. 

 

 

 

 

 

 

 

 

 

참고: medium.com/underrated-data-structures-and-algorithms/trie-data-structure-fd9a2aa6fcb8