[자료구조] 트라이(Trie) 정리 (TS)

little giant·2024년 10월 31일
0

알고리즘

목록 보기
1/2

자동 완성, 사전 구현, 접두사 검색등에 사용되는 트라이(Trie)라는 자료구조에 대해 정리한 글입니다.

Trie (트라이)는 문자열을 저장하고 검색하는 데 효율적인 트리 기반 데이터 구조이며
문자열의 공통 접두사를 공유하여 메모리를 절약하고 탐색 속도를 높일 수 있습니다.

Trie의 구조와 특징

  1. 노드와 엣지: 트라이의 각 노드는 알파벳 문자에 해당하며, 각 엣지는 문자에 따라 연결됩니다. 노드는 단어의 끝을 표시하는 플래그를 가질 수 있습니다.
  2. 루트 노드: 항상 비어 있으며, 문자열이 삽입될 때는 루트 노드에서부터 시작합니다.
  3. 공통 접두사 공유: 트라이는 접두사를 공유할 때 공통된 부분을 중복 저장하지 않기 때문에 메모리 절약 효과가 있습니다.
  4. 탐색 및 삽입 시간: 문자열의 길이가 (L)이라면 삽입과 탐색의 시간 복잡도는 (O(L))로 매우 빠릅니다.

Trie의 주요 연산

  • 삽입 (Insert): 문자열을 하나씩 루트부터 따라가면서 트리에 삽입합니다. 만약 중간에 해당 문자가 없다면 새 노드를 추가합니다.
  • 탐색 (Search): 찾고자 하는 문자열을 루트부터 따라가며 일치하는지를 확인합니다. 끝까지 일치하면 존재하는 것이고, 중간에 끊기면 없는 문자열입니다.
  • 삭제 (Delete): 삭제 시, 해당 문자열의 마지막 노드까지 찾아가서 삭제를 표시하거나, 더 이상 필요 없는 노드들을 정리합니다.
  • 접두사 검색 (Prefix Search): 접두사가 일치하는 노드를 찾아 그 노드로부터 아래에 연결된 모든 단어를 반환합니다. 이는 자동 완성 기능에 유용합니다.

트라이의 장단점

  • 장점:
    • 빠른 검색 속도: 문자열 검색이 매우 빠르고, 특히 접두사 검색에 유리합니다.
    • 메모리 효율성: 동일한 접두사는 공유하므로 메모리가 절약됩니다.
  • 단점:
    • 알파벳 개수에 따른 메모리 사용: 특히 알파벳이 많을 경우 트라이의 노드 수가 많아져 메모리 사용량이 증가할 수 있습니다.

예시

다음과 같은 문자열 집합이 있다고 가정합니다: ["cat", "car", "can", "dog"]

트라이 구조는 다음과 같이 구성됩니다:

  • "c"에서 시작하는 공통 접두사를 공유합니다.
  • 각 문자가 노드가 되고, 문자열 끝에는 단어의 끝임을 표시합니다.

이 구조를 통해 "ca"로 시작하는 모든 단어를 쉽게 찾을 수 있습니다 (e.g., "cat", "car", "can").

구현

트라이(Trie)를 타입스크립트로 구현하는 방법을 설명하겠습니다. 트라이는 기본적으로 트리 구조를 활용하여 각 노드가 특정 문자에 해당하며, 단어의 끝을 표시할 수 있도록 합니다.

1. TrieNode 클래스 정의

각 노드는 자신의 자식 노드와 단어의 끝인지 여부를 가지고 있어야 합니다.

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}
  • children: 각 문자를 키로 하고, 해당 문자에 연결된 노드를 값으로 하는 맵입니다.
  • isEndOfWord: 해당 노드가 단어의 끝을 나타내는지 여부를 나타내는 불리언 값입니다.

2. Trie 메소드 정의

트라이 클래스는 단어를 삽입하고 검색하며, 접두사 기반 검색을 할 수 있는 메서드를 포함합니다.

class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  // 단어 삽입
  insert(word: string): void {
    let current = this.root;

    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char)!;
    }
    current.isEndOfWord = true;
  }

  // 단어 검색
  search(word: string): boolean {
    let current = this.root;

    for (const char of word) {
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char)!;
    }
    return current.isEndOfWord;
  }

  // 키워드로 시작하는 모든 단어 반환
  startsWith(prefix: string): string[] {
    let current = this.root;

    // 1. 접두사에 해당하는 노드로 이동
    for (const char of prefix) {
      if (!current.children.has(char)) {
        return []; // 접두사가 없으면 빈 배열 반환
      }
      current = current.children.get(char)!;
    }

    // 2. 접두사 이후의 모든 단어 수집
    const results: string[] = [];
    this.collectWords(current, prefix, results);
    return results;
  }

  // 헬퍼 함수: 특정 노드부터 시작해 단어들을 수집
  private collectWords(node: TrieNode, prefix: string, results: string[]): void {
    if (node.isEndOfWord) {
      results.push(prefix); // 단어 끝에 도달하면 결과에 추가
    }

    for (const [char, childNode] of node.children) {
      this.collectWords(childNode, prefix + char, results); // 자식 노드들에 대해 재귀 호출
    }
  }
}

메서드 설명

  • insert(word: string): void: 단어를 트라이에 삽입하는 메서드입니다. 각 문자를 따라가며 노드를 추가하고, 단어의 마지막 노드에서는 isEndOfWord를 true로 설정합니다.
  • search(word: string): boolean: 단어가 트라이에 존재하는지 확인합니다. 존재하면 true, 없으면 false를 반환합니다.
  • startsWith(prefix: string): string[]: 주어진 prefix로 시작하는 모든 단어를 트라이에서 찾아 반환합니다.
    • 먼저 주어진 prefix를 따라가면서 존재하는지 확인하고, 만약 접두사가 없으면 빈 배열을 반환합니다.
    • 접두사가 존재하면 collectWords를 호출하여 해당 노드 아래의 모든 단어를 results 배열에 수집합니다.
  • collectWords(node: TrieNode, prefix: string, results: string[]): void: 재귀적으로 트라이의 특정 노드에서 시작하는 모든 단어를 수집하는 헬퍼 함수입니다.

3. 사용 예시

const trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("can");
trie.insert("dog");

console.log(trie.startsWith("ca")); // ["cat", "car", "can"]
console.log(trie.startsWith("do")); // ["dog"]
console.log(trie.startsWith("z"));  // []

위 예시에서 cat, car, can을 삽입하고 검색 및 접두사 검사를 수행합니다.

Trie와 배열을 각각 사용하여 문자열을 저장하고 검색, 삽입, 삭제하는 경우, 시간 복잡도와 공간 복잡도는 상당히 다르게 나타납니다. 두 자료구조의 복잡도를 비교해보겠습니다.

Array 사용 방식과의 비교

1. 시간 복잡도 비교

연산Trie 시간 복잡도배열 시간 복잡도 (includes / push / remove)
탐색(O(L))(O(N ⋅ L))
삽입(O(L))(O(1)) (평균) , (O(N ⋅ L)) (중복 체크)
삭제(O(L))(O(N ⋅ L))

시간 복잡도 상세 설명

  • L: 문자열의 길이
  • N: 배열에 저장된 문자열의 수

  1. 탐색 (Search)

    • Trie: 문자열 길이가 (L)인 경우, 각 문자마다 다음 노드를 탐색하므로 (O(L))의 시간 복잡도가 소요됩니다.
    • 배열: 배열의 각 원소와 일일이 비교해야 하므로 (O(N ⋅ L)) 시간이 필요합니다. 배열에 includes 메서드를 사용할 때, 최악의 경우 배열의 모든 원소를 검색해야 합니다.

  2. 삽입 (Insert)

    • Trie: 문자열을 삽입할 때 각 문자를 따라가며 노드를 추가하므로 (O(L))입니다.
    • 배열: 배열에 문자열을 추가하는 것은 평균적으로 (O(1)) 시간이 소요됩니다. 그러나 중복을 방지하기 위해 이미 있는지 확인하려면 (O(N ⋅ L))의 추가 비용이 발생할 수 있습니다.

  3. 삭제 (Delete)

    • Trie: 문자열의 길이에 비례하여 (O(L))의 시간이 소요됩니다.
    • 배열: remove 메서드는 삭제할 요소를 검색하고 제거해야 하므로, 최악의 경우 배열을 모두 검색해야 하며 (O(N ⋅ L))의 시간 복잡도를 가집니다.

2. 공간 복잡도 비교

연산Trie 공간 복잡도배열 공간 복잡도
저장 용량(O(∑L))(O(N ⋅ L))

공간 복잡도 상세 설명

  • Trie: Trie는 각 문자마다 노드를 생성하며, 같은 접두사를 공유하기 때문에 저장된 단어들의 모든 문자 수의 합에 비례하여 공간을 차지합니다. 이 복잡도는 (O(∑{L}))로 나타낼 수 있으며, 접두사를 공유하는 경우에는 배열보다 메모리를 절약할 수 있습니다.
  • 배열: 배열에 (N)개의 단어를 저장하면, 각 단어가 길이 (L)을 가지므로 총 공간 복잡도는 (O(N ⋅ L))입니다. 접두사를 공유하지 않고 단순 저장만 하므로 중복이 포함된 경우 메모리 사용량이 더 많아질 수 있습니다.

요약

  • 시간 복잡도: Trie는 탐색과 삭제에서 배열보다 효율적입니다, 특히 문자열의 길이가 길고, 저장된 데이터가 많은 경우 배열보다 유리합니다.
  • 공간 복잡도: Trie는 접두사를 공유하여 메모리를 절약할 수 있으며, 특히 중복된 접두사가 많은 경우 배열보다 공간 효율이 높습니다.
profile
little giant
근성 타입 개발자

0개의 댓글