[자료구조] javascript 트라이 (Trie)

javascript 에서 트라이 자료구조에 대해서 알아보자

트라이 자료구조의 주요 특징은 빠른 탐색 속도, 메모리 효율성, 그리고 문자열 검색에 용이하다는 것입니다. 각 문자마다 노드를 가지기 때문에 검색 과정에서 다음 문자로의 이동이 빠르고 효율적입니다. 또한 문자열이 겹치는 부분이 많아도 중복된 노드를 공유하여 메모리를 절약할 수 있습니다. 이러한 특징으로 인해 트라이 자료구조는 대용량의 문자열 데이터를 효율적으로 처리할 수 있습니다.

트라이 구현

class Node {
  constructor(value = ""){
    this.value = value;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }
  // 추가
  insert(string){
    let currentNode = this.root;

    for(const char of string){
      if(!currentNode.children.has(char)){
        currentNode.children.set(
          char,
          new Node(currentNode.value + char)
          );
      }
      currentNode = currentNode.children.get(char);
    }
  }
  // 조회
  has(string){
    let currentNode = this.root;

    for(const char of string){
      if(!currentNode.children.has(char)){
        return false;
      }
      currentNode = currentNode.children.get(char);
    }
    return true;
  }  
}

const trie = new Trie();

활용 예시

자동 완성 기능, 철자 검사 및 교정, 문자열 패턴 매칭 등

자동 완성 기능 : 사용자가 입력한 문자열에 대해 가능한 후보 단어를 빠르게 제공하여 사용자 경험을 향상시킵니다.
철자 검사 및 교정: 올바르지 않은 철자를 가진 문자열을 효율적으로 식별하고 교정할 수 있습니다.
문자열 패턴 매칭: 특정 패턴을 가진 문자열을 효율적으로 찾아내는 데에 사용됩니다.

[자료구조] javascript 트라이 (Trie)

javascript 에서 트라이 자료구조에 대해서 알아보자

목차

트라이 자료구조란

트라이 구조의 특징

트라이 구현

활용 예시

자동 완성 기능, 철자 검사 및 교정, 문자열 패턴 매칭 등