트라이

트라이

ex) 자동완성, 사전 찾기
L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼 걸림
정점이 자식에 대한 링크를 전부 가지고 있어 공간 많이 사용

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

코드로 구현

트라이 구성

// 트리 자료구조 -> 노드 필요
// 인접 리스트 형태로 구현
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) {
      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;
      
      // 문자열 순회, 없으면 false 리턴
      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