트라이 (Trie) 란?

주로 문자열을 저장하고 검색하는 데 사용되는 효율적인 자료구조. 트라이는 특히 사전과 같은 어휘 집합을 관리하거나, 자동완성, 패턴 매칭 등의 응용 프로그램에서 유용.

트라이의 구조

트라이는 트리 형태의 자료구조로, 각 노드는 하나의 문자를 나타내며, 루트 노드는 비어있음. 문자열의 각 문자는 노드를 통해 연결되어 있음.
트라이의 각 경로는 문자열의 접두사(prefix)를 나타냄

트라이의 주요 특징

1. 빠른 검색 속도 : 문자열의 길이에 비례하는 시간 복잡도로 검색할 수 있음
2. 메모리 사용 : 공간 복잡도는 저장하는 문자열의 길이에 비례하며, 동일한 접두사를 공유하는 문자열은 메모리를 절약 할 수 있음.
3. 접두사 검색 : 특정 접두사로 시작하는 모든 문자열을 빠르게 찾을 수 있음.

트라이의 주요 연산

1. 삽입(Insert) : 문자열을 트라이에 삽입. 문자열의 각 문자를 차례로 따라가면서 노드를 생성하거나 기존 노드를 사용

2. 검색(Search) : 문자열이 트라이에 존재하는지 확인. 문자열의 각 문자를 차례로 따라가면서 노드가 존재하는지 확인

3. 삭제(Delete) : 문자열을 트라이에서 삭제. 이는 삽입의 반대 과정으로, 문자열의 각 문자를 차례로 따라가면서 노드를 삭제

4. 접두사 검색(Prefix Search) : 특정 접두사로 시작하는 모든 문자열을 찾음. 접두사를 따라가며 트라이를 탐색

트라이의 시간복잡도

1. 삽입연산

• 시간복잡도 : O(L)
• L은 삽입하는 문자열의 길이
• 각 문자마다 새로운 노드를 생성하거나 이미 존재하는 노드로 이동

2. 검색연산

• 시간복잡도 : O(L)
• L은 검색하는 문자열의 길이
• 각 문자마다 해당 노드가 존재하는지 확인

3. 접두사 검색연산

• 시간복잡도 : O(L)
• L은 접두사의 길이
• 각 문자마다 해당 노드가 존재하는지 확인

4. 삭제연산

• 시간복잡도 : O(L)
• L은 삭제하는 문자열의 길이
• 각 문자마다 해당 노드를 확인하고, 필요한 경우 노드를 삭제

트라이의 효율성

• 트라이는 문자열의 길이에 비례하는 시간복잡도를 가지므로, 문자열의 길이가 짧을수록 매우 효율적.
• 해시테이블과 비교할때, 트라이는 접두사 검색에 매우 유리. 해시 테이블은 정확한 문자열 검색에는 효율적이지만, 접두사 검색에는 효율적이지 않음
• 트라이는 메모리를 많이 사용할수 있음. 특히, 노드의 자식노드 배열을 전부 초기화할 경우 메모리 사용량이 커짐. 이를 줄이기 위해 자식 노드를 동적으로 할당하거나, 압축 트라이(컴팩트 트라이, 패트리샤 트라이) 를 사용할 수 있음.