[Typescript] Trie (트라이) 자료구조 직접 구현하기

 

 

프로젝트에서 자동 완성 컴포넌트를 구현하면서 트라이 자료구조를 접했는데 이번 기회에 직접 구현해보려 한다. 언어는 타입 안정성을 위해 Typescript를 사용했다.

 

 

 

Trie (Prefix Tree)

Trie는 문자열을 빠르게 탐색할 수 있는 자료구조로, 트리 형태로 구성된다. Prefix tree라고도 불린다.

각 노드는 문자열의 한 글자를 나타내며, 루트부터 마지막 노드까지의 경로가 문자열을 구성한다. 해시 테이블에 비해 접두사 기반의 검색에서 더 효율적이다.

문자열을 각 노드에 저장하고 메모리를 사용하지만 탐색 속도가 O(N)으로 매우 빠른 편이다. 따라서 자동 완성이나 사전 검색, 맞춤법 검사와 같이 문자열을 활용하는 기능에 주로 사용된다.

 

 

시간 복잡도

Operation	Average	Worst
Insert	O(N)	O(N)
Search	O(N)	O(N)
Delete	O(N)	O(N)

 

• 문자열의 길이만큼 순회/재귀를 반복하기 때문에 최악의 케이스에서도 O(N)이다.

 

 

공간 복잡도

Operation	Average	Worst
Space	O(NM)	O(NM)

• N : 문자열 길이의 평균
• M : 저장된 문자의 개수
• 저장된 문자의 개수 O(M) 만큼 실행 O(N) 하기 때문에 공간 복잡도는 O(NM)이다.

 

 

주요 구조와 기능

 

Node

• 각 노드는 key, value, child를 갖고 있다.
  • key : 현재 노드의 문자
  • value : null 혹은 삽입된 문자열 전체. 단어의 끝인지 여부를 알려준다.
  • child : 자식 노드. Map 자료구조를 사용한다.

class Node<T> {
  key: string;
  value: T | null;
  child: Map<string, Node<T>>;

  constructor(key = '', value = null) {
    this.key = key;
    this.value = value;
    this.child = new Map();
  }
}

 

 

Root Node

• 루트 노드는 항상 비어있다.

Last Node

• 마지막 노드인 경우 value에 문자열이 들어간다.
• 마지막 노드가 아닌 경우 value는 null이다.

insert

• 문자열의 각 문자를 차례대로 탐색한다.
• 루트 노드부터 시작하여, 자식 노드에 문자가 있는지 확인한다.
  • 문자가 없다면 자식 노드에 추가하고
  • 문자가 있다면 타고 들어간다.
• 마지막 문자에 도달하면 value에 문자열을 넣어 마지막 노드임을 표시한다.

 

예시 - Apple을 자료구조에 Apple을 저장할 때

const trie = new Trie()
trie.insert('Apple', 'Apple')

• 루트 노드부터 시작하여, 첫 번째 단어인 "A"가 자식 노드에 존재하는지 확인한다.
• 자식 노드에 없는 경우, "A" 노드를 추가한다.
  • 자식 노드에 존재하는 경우, 해당 노드로 이동한다.
• "A" 노드로 이동하여 위 과정을 반복한다.
• 마지막인 "e" 문자의 노드에 도달한 경우, value에 Apple을 저장한다.

 

insert(key: string, value: T): void {
  let currentNode = this.root;

  for (let i = 0; i < key.length; i++) {
    const word = key[i];
    // child가 없으면 새로운 노드 생성
    if (!currentNode.child.has(word)) {
      currentNode.child.set(word, new Node(word));
    }
    currentNode = currentNode.child.get(word)!;
  }
  currentNode.value = value;
}

 

• 이때 value를 제네릭으로 설정해주었다. insert를 사용하는 곳에서 원하는 정보를 트리에 저장해줄 수 있도록 구현했다.
• 전화번호부를 예로 들자면, "김철수"라는 이름을 가진 사람의 연락처 "010-1234-5678"을 저장하려고 한다. "김"부터 "철", 마지막 글자인 "수" 노드를 생성한 뒤 제네릭 타입을 통해 "수" 노드의 value에 { mobile: "010- 1234-5678" }을 저장할 수 있게 된다. 따라서 사용자가 원하는 데이터를 어떤 타입이든 저장하고 활용할 수 있다.

 

 

search

• 루트 노드부터 탐색을 시작한다.
• 자식 노드를 타고 들어가며 마지막 문자에 도달한 경우 value가 존재한 지 확인한다. value가 null인 경우 유효하지 않는 단어로 간주한다.
• 자식 노드에 찾고자 하는 문자가 없는 경우 즉시 종료한다.
  
  

예시 - Apple에 어떤 값이 저장되어 있는지 찾고 싶을 때

const trie = new Trie()
trie.insert('Apple', 'Apple')

trie.search('Apple')

• 루트 노드부터 시작하여 자식 노드에 "A"가 있는지 확인한다.
• "A" 노드가 있다면 해당 노드로 이동한다.
  • 노드가 없다면 즉시 종료한다.
• 마지막 문자에서 value가 null이 아닌지 확인한다.
  • null이 아닌 경우 마지막 노드에 저장된 value 반환

search(key: string): T | null {
  let currentNode = this.root;

  for (let i = 0; i < key.length; i++) {
    const word = key[i];
    // 자식 노드가 있을 때
    if (currentNode.child.has(word)) {
      currentNode = currentNode.child.get(word)!;
    }
  }
  return currentNode.value ?? null;
}

 

 

 

delete

• 마지막 노드로 이동하여 재귀적으로 탐색한다.
• value를 null로 업데이트한다.
• child의 size가 0인 경우 (자식 노드가 없는 경우) 해당 노드를 삭제한다.

예시 - 저장된 Apple을 삭제하고 싶을 때

const trie = new Trie()
trie.insert('Apple', 'Apple')

trie.delete('Apple')

• Apple의 마지막 노드인 e로 이동한다.
• e 노드의 value를 null로 업데이트한다.
• 부모 노드로 이동한다.
• 자식 노드(e 노드)의 child의 size가 0이라면 e 노드를 삭제한다.

 

delete(key: string): void {
  this.deleteFunc(this.root, key, 0);
}

private deleteFunc(node: Node<T>, key: string, index: number): boolean {
  // 마지막 노드로 이동하여 재귀적으로 자식 탐색
  if (index === key.length) {
    if (node.value === null) {
      return false;
    }
    node.value = null;
    return node.child.size === 0;
  }

  const char = key[index];
  const childNode = node.child.get(char);

  if (!childNode || !this.deleteFunc(childNode, key, index + 1)) {
    return false;
  }
  node.child.delete(key);
  return node.value === null && node.child.size === 0;
}

 

 

 

 

 

전체 코드

class Node<T> {
  key: string;
  value: T | null;
  child: Map<string, Node<T>>;

  constructor(key = '', value = null) {
    this.key = key;
    this.value = value;
    this.child = new Map();
  }
}

export class Trie<T> {
  private root: Node<T>;

  constructor() {
    this.root = new Node<T>();
  }

  insert(key: string, value: T): void {
    let currentNode = this.root;

    for (let i = 0; i < key.length; i++) {
      const word = key[i];
      // child가 없으면 새로운 노드 생성
      if (!currentNode.child.has(word)) {
        currentNode.child.set(word, new Node(word));
      }
      currentNode = currentNode.child.get(word)!;
    }
    currentNode.value = value;
  }

  search(key: string): T | null {
    let currentNode = this.root;

    for (let i = 0; i < key.length; i++) {
      const word = key[i];
      // 자식 노드가 있을 때
      if (currentNode.child.has(word)) {
        currentNode = currentNode.child.get(word)!;
      }
    }
    return currentNode.value ?? null;
  }

  delete(key: string): void {
    this.deleteFunc(this.root, key, 0);
  }

  private deleteFunc(node: Node<T>, key: string, index: number): boolean {
    // 마지막 노드로 이동하여 재귀적으로 자식 탐색
    if (index === key.length) {
      if (node.value === null) {
        return false;
      }
      node.value = null;
      return node.child.size === 0;
    }

    const char = key[index];
    const childNode = node.child.get(char);

    if (!childNode || !this.deleteFunc(childNode, key, index + 1)) {
      return false;
    }
    node.child.delete(key);
    return node.value === null && node.child.size === 0;
  }
}

 

 

 

 

• 마지막 노드를 나타내는 프로퍼티 (value)를 boolean으로 설정했다가 외부에서 주입받는 타입을 활용하기로 바꿨다. Trie 자료구조를 사용하는 목적을 생각해 봤을 때 자동 완성처럼 '원하는 값이 인스턴스에 저장되어 있는지'를 확인할 뿐만 아니라 전화번호부처럼 '원하는 값이 인스턴스에 저장되어 있고 그 단어에 매핑된 값은 무엇인지'를 확인하는 경우도 있겠다고 생각하여 제네릭 기반으로 설계했다.
• class를 Typescript로 구현해보는 것은 처음이라 타입 지정이 꽤나 어려웠지만 .. 열심히 구글링한 덕분에 자료구조를 만들 수 있었다.