[javascript] 레트리 (Retrie) 데이터 구조

08 Dec 2023

javascript

레트리 (Retrie)는 문자열 검색 및 저장을 위한 효율적인 데이터 구조입니다. 이 데이터 구조는 트리 형태로 키-값 쌍을 저장하여 빠른 검색을 가능하게 합니다. 주로 자연어 처리, 검색 엔진, 트라이트리 공 문자 검색 등에서 사용됩니다.

레트리의 구조

레트리는 여러 개의 노드로 구성된 트리 구조입니다. 각 노드는 문자나 다른 데이터와 연결된 링크를 가지고 있습니다. 문자열을 삽입하거나 조회할 때, 루트 노드로부터 시작하여 각 문자에 해당하는 링크를 따라 이동하면 됩니다. 검색 시간은 입력된 문자열의 길이에 비례하여 증가하므로 매우 빠른 검색이 가능합니다.

레트리의 활용

레트리는 특히 문자열 검색 및 자연어 처리에 유용하게 활용됩니다. 예를 들어, 사전 검색이나 자동완성 기능을 구현할 때 레트리가 효율적으로 사용될 수 있습니다. 또한, 트라이트리라고 불리는 형태의 레트리는 공통 접두어를 가진 문자열을 저장하고 검색하는 데 유용합니다.

// 레트리 구현 예시

class Node {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new Node();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

// 사용 예시
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false

레트리 데이터 구조는 다양한 애플리케이션에서 문자열 검색을 효율적으로 수행하기 위한 강력한 도구로 활용될 수 있습니다.

레트리의 구조

레트리의 활용

참고 자료