[자료구조와 알고리즘] 208. Implement Trie (Prefix Tree)

그림 출처: https://www.interviewbit.com/data-structure-interview-questions/

문제 설명

leetcode Top Interview 150 - 208. Implement Trie (Prefix Tree)
자료 구조 중에 하나인 Trie 트라이를 구현해보는 문제입니다.

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
트라이 자료 구조는 트리 자료 구조중 하나로서 문자열 데이터셋의 키를 저장하고 꺼내는 데 효율적인 자료 구조입니다. 자동완성과 스펠링체커 등 다양한 애플리케이션에 쓰입니다.

Implement the Trie class:
Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
트라이 자료 구조 구현하기:
trie 객체는 Trie()로 초기화합니다.
insert 메서드는 trie 객체에 단어를 입력하는 메서드입니다.
search 메서드는 trie 객체에 단어가 있으면 true 없으면 false를 반환합니다.
startsWith 메서드는 trie 객체에 prefix로 주어지는 글자로 시작하는 단어가 존재하면 true 존재하지 않으면 false를 반환합니다.

풀어보기

// 트라이 자료 구조에서 사용할 노드를 먼저 생성
function Node() {
    this.isEndOfWord = false;
    this.children = {};
}
// Trie()로 새로운 객체를 생성할 때 root 노드 생성
var Trie = function() {   
    this.root = new Node();
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  	// root 노드에서부터 순서대로 접근
    let node = this.root;
    for (let char of word) {
        if (!node.children[char]) {
            const newNode = new Node();
            node.children[char] = newNode;
            node = newNode;
        } else {
            node = node.children[char];
        }
    }
  	// 단어의 마지막 글자가 들어간 노드의 isEndOfWord 속성에는 true
    node.isEndOfWord = true
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.root
    for (let char of word) {
        if (!node.children[char]) {
            return false
        } else {
            node = node.children[char]
        }
    }
  	// 단어의 마지막에만 isEndOfWord속성이 true이므로 그 경우에만 true
    return node.isEndOfWord? true : false
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.root;
    for (let char of prefix) {
      	// 자식 노드가 한번이라도 없다면 단어가 한 개도 없으므로 false
        if (!node.children[char]) {
            return false
        } else {
            node = node.children[char]
        }
    }
  	// 자식 노드가 하나라도 있으면 true 없으면 false
    // prefix만으로 구성된 단어가 있는 경우도 있으므로 isEndOfWord도 검사
    return (Object.keys(node.children).length !== 0 || 
            node.isEndOfWord)? 
true : false
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

구현만 해보는 문제이기 때문에 복잡도에서 큰 차이가 없는 것으로 보입니다!

Class 문법으로 구현하기

class Trie {
  constructor() {
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    for (let c of word) {
      if (node[c] == null) node[c] = {};
      node = node[c];
    }
    node.isWord = true;
  }

  // 노드를 찾는 과정을 공통 메서드로 추출 -> search, startsWith 메서드에서 사용
  traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }

  startsWith(prefix) {
    return this.traverse(prefix) != null;
  }
}

마무리

접두사(prefix) 검색, 사전 검색, 자동 완성에 유리한 자료 구조인 트라이 자료 구조를 직접 구현해보면서 트리 구조로 문자열을 효과적으로 검색할 수 있는 구조를 생각할 수 있었습니다! 실생활에서 매일 접하는 기능이어서 더 흥미로운 자료 구조였습니다. 👩‍💻💖