트라이

트라이란?

• 문자열을 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 검색(reTRIEve)이라는 단어에서 유래되었으며, 검색엔진이나 자동완성 등에서 사용된다.
• 자식 노드의 포인터를 저장해야하므로 저장 공간이 추가로 요구된다. (배열 또는 HashMap 사용)

시간 복잡도

• 원소 삽입, 삭제, 탐색: O(M) (M은 문자열의 길이)

원소 탐색 과정

1. 루트의 자식 노드에서 첫번째 글자를 찾는다.

2. 첫번째 글자의 자식 노드에서 다음 글자를 찾는다.

3. 마지막 글자에 해당하는 노드가 존재하고, 노드에 실제 값이 존재하면 탐색 성공

 

*삽입과 삭제도 위 탐색 과정을 거친 후, 노드를 추가하거나 삭제하면 된다.