트라이

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

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

실무 사용 예시 : 검색어 자동완성

2-1 트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 으용
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용

2-2 트라이 구조

• 루트는 비어있다.
• 각 간선(링크)은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현 가능

3. 코테
   핵심 키워드 : 문자, 학습, 자동완성
   대표문제 : 자동완성

   

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);
    }
  }
}

const trie = new Trie();