[JS] 트라이

검색의 자동완성 기능을 구현할 때 적합한 자료구조

 

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

 

특징

- 찾는 문자열의 길이만큼만 시간 복잡도가 걸린다.

- 저장공간을 좀 더 많이 사용한다.

 

---

구조

루트는 비어있다.

각 간선은 추가될 문자를 키로 가진다.

각 정점은 이전 간선의 키를 값으로 가진다.

해시 테이블과 연결 리스트를 사용한다.

 

---

트리 생성하기

function makeTrie(words) {
  const root = {}; // 먼저 루트 노드를 설정할 변수를 만든다.
  for (const word of words) { // Trie를 구성하기 위한 루프를 돌린다.
    let current = root; // 루프부터 시작
    for (const letter of word) { // 단어의 글자를 하나씩 춫출한 후
      if (!current[letter]) current[letter] = [0, {}]; // 값을 넣는다. 리스트의 첫 번째 값은 학습된 단어가 몇 개인지를 카운팅하고 두 번째 값은 트리 구조로 이용할 노드 값으로 사용한다.
      current[letter][0] = 1 + (current[letter][0] || 0); // 카운팅을 위해 1 더해준다.
      current = current[letter][1]; // current는 letter에 해당되는 노드로 이동한다.
    }
  }
  return root; // 반환
}

 

트라이 

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