트라이 (Trie)

Jun 2k (Jun2)·2023년 9월 27일

CS지식 WIL cs공부 자료구조&알고리즘

자료구조&알고리즘

목록 보기

12/19

트라이

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
검색창의 문자 자동 완성 기능이 대표적인 사용 예이다.

출처: 이선협 강사님 데브코스 강의 자료

트라이의 특징

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

Trie 생성하기

Trie 구조

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

JavaScirpt에서 Trie 구현하기

Trie 구성

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();
trie.insert('cat');
trie.insert('can');
console.log(trie.has('cat')); // true
console.log(trie.has('can')); // true
console.log(trie.has('cap')); // false