[Algorithm]Trie

Trie

Trie 자료구조는 문자열을 검색할 때 자주 사용된다. 검색창에서의 ap까지만 입력해도 나오는 apple, 등을 구현할 때 주로 쓰인다.

특히 잘 쓰이다 보니 코딩테스트에서 효율성을 고려한 문제로 자주 나오는 것같다. 단어를 검색하려고 하다보면, M의 길이를 가지는 문자 N개를 확인하려면 아래와 같은 이중for문을 사용해야 하기 때문에 O(M * N^2)의 시간 복잡도를 가질 것이다.

  for(word of words){
	for(let i=0;i<word.length;i++){
		if(word[i]!==query[i])
           //확인 후 동작
    }
          
}

Trie 자료구조를 사용하면 O(MN)의 시간복잡도를 가진다. 그렇기 때문에 효율성 측면에서 뛰어나게 되는 것이다.

Trie 구현

function TrieNode(){
 	this.children={};
  	this.endOfWord=false;
}

function Trie(){
  this.root=new TrieNode()
}

삽입

글자가 children에 들어있는지 확인하고 없을 경우, children[ch]에 새로운 TrieNode를 선언해 준다.

Trie.prototype.insert=function(word){
  let current = this.root;
  for(let i=0;i<word.length;i++){
    const ch = word[i];
    let node = current.children[ch];
    
    if(node==undefined){
      node=new TrieNode();
      current.children[ch]=node;
    }
    
    current=node;
  }
  current.endOfWord=true;
}

Search

글자를 확인하고 마지막에 current.endOfWord의 boolean 값을 return 하여 유무를 확인한다.

Trie.prototype.search=function(word){
  let current=this.root;
  for(let i=0;i<word.length;i++){
    const ch= word[i];
    let node = current.children[ch];
    
    if(node===undefined){
      return false;
    }
    
    current = node;
  }
  return current.endOfWord
}