트라이(Trie)

트라이(Trie)란?

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다.

노드의 계층 구조로 구성되며, 각 노드가 문자열의 한 문자 또는 키의 일부를 나타낸다.

문자열을 저장할 때, 공통된 접두사는 공유하도록 설계되어 공간 효율성이 높다.

 

 

 

트라이의 구조

 

• 루트 노드: 트리의 시작점으로, 문자열 집합에 공통된 접두사가 없는 최상위 노드.
• 자식 노드: 한 문자씩 연결되며, 문자열의 경로를 형성.
• 종료 표시: 단어가 끝날 때 해당 노드에 플래그 또는 값을 설정. (위 그림에서는 빨간 원이 그 역할을 함)

 

예시) 문자열 ["cat", "car", "dog"]를 트라이에 저장한 경우

        (root)
        /    \
      c       d
     / \       \
    a   a       o
   /     \       \
  t       r       g

 

 

 

 

트라이 연산

삽입 (Insert)

1. 루트 노드에서 시작.
2. 문자열의 각 문자를 따라가며 적절한 노드로 이동.
3. 경로가 없다면 새 노드를 생성.
4. 문자열이 끝날 때 해당 노드에 "종료 표시"를 설정.

 

탐색 (Search)

1. 루트 노드에서 시작.
2. 문자열의 각 문자를 따라가며 적절한 노드로 이동.
3. "종료 표시"가 있는 노드에까지 도달하면 탐색 문자열이 존재하는 것임.

 

삭제 (Delete)

1. 문자열을 검색하여 경로를 따라 이동.
2. 문자열이 끝나는 노드에서 "종료 표시"를 제거.
3. 삭제 후 자식 노드가 없는 경우, 해당 노드를 제거 (재귀적으로 수행).

 

접두사 탐색 (Prefix Search)

1. 접두사의 경로를 따라 트라이에서 탐색.
2. 접두사의 마지막 노드에서 시작하여 모든 자식 노드를 탐색.

 

 

 

트라이의 특성과 장단점

특성

1. 계층적 구조: 각 노드가 한 문자를 나타내며, 루트에서 리프 노드까지의 경로가 문자열을 형성한다.
2. 공통 접두사 공유: 같은 접두사를 가진 문자열은 트리에서 공통된 경로를 공유한다.
3. 종료 표시: 문자열이 끝나는 위치를 나타내기 위해 종료 노드에 특별한 표시(예: isEndOfWord 플래그)를 둔다.
4. 고정된 자식 수: 일반적으로 알파벳(예: 26자) 또는 유니코드 문자 범위에 기반한 고정 크기의 배열을 사용하여 각 노드의 자식을 관리한다.

장점

• 문자열 탐색이 매우 빠르다. 찾고자 하는 문자열의 길이가 n일 때 탐색 복잡도는 O(n)
• 문자열 삽입도 O(n)시간에 가능하다.
• 공통 접두사를 공유하는 문자열을 효율적으로 저장할 수 있다.
• 문자열을 사전순으로 저장하여 정렬된 상태를 유지한다.

단점

• 메모리 사용량이 크다. 각 노드가 다음 문자에 대한 포인터를 가지고 있어야 하기 때문.
• 구현이 다른 자료구조에 비해 복잡하다. 특히 삭제 연산이 까다롭다.

 

 

 

트라이 활용

1. 문자열 검색
   • 사전 구현(단어 존재 여부 확인)
   • 검색 엔진의 자동 완성(Autocomplete)
2. 접두사 검색
   • 키워드 추천 시스템
   • 파일 시스템 경로 검색
3. 데이터 압축
   • 공통된 접두사를 저장하여 데이터 압축 효과 제공
4. 패턴 매칭
   • 특정 문자열 집합에서 빠르게 패턴을 찾는 데 사용
5. DNS 조회
   • URL이나 IP 주소를 효율적으로 관리

 

 

⭐️ 트라이와 다른 자료구조의 비교

해시 테이블
- 해시 테이블은 접두사 검색이 비효율적, 트라이는 효율적.
- 해시 테이블은 특정 키 검색에서 더 효율적일 수 있음.

이진 탐색 트리
- 트라이는 문자열 데이터에 특화.
- 이진 탐색 트리는 일반적인 키에 대해 사용됨. 

즉, 문자열 데이터에 대한 연산이 필요할 때, 접두사 검색이 필요할 때 트라이 사용을 고려해볼 수 있음.