[바미] Tree algorithms - Trie trees 구현하기.

Trie tree?

Trie tree는 문자열 검색을 효율적으로 수행하기 위한 트리 자료구조입니다.

이진 트리와는 달리 한 노드당 여러 개의 자식 노드를 가지며, 각 자식 노드는 해당 위치에 올 수 있는 문자를 나타내는 것이 특징이죠.

 

코드 구현

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      let ch = word.charAt(i);
      let node = current.children[ch];
      if (!node) {
        node = new TrieNode();
        current.children[ch] = node;
      }
      current = node;
    }
    current.isEndOfWord = true;
  }

  search(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      let ch = word.charAt(i);
      let node = current.children[ch];
      if (!node) {
        return false;
      }
      current = node;
    }
    return current.isEndOfWord;
  }
}

코드 설명

TrieNode 클래스는 Trie tree의 노드를 나타내고, Trie 클래스는 Trie tree를 구현하는 클래스에요.

Trie 클래스는 insert() 메소드와 search() 메소드를 제공하고 있죠.

  insert(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      let ch = word.charAt(i);
      let node = current.children[ch];
      if (!node) {
        node = new TrieNode();
        current.children[ch] = node;
      }
      current = node;
    }
    current.isEndOfWord = true;
  }

insert() 메소드는 Trie tree에 새로운 단어를 추가하는 메소드인데 먼저, 현재 노드를 루트 노드로 초기화해요.

그리고 단어의 각 문자를 순회하며 해당 문자를 나타내는 자식 노드가 있는지 검사하죠. 이 때 만약 해당 자식 노드가 없다면 새로운

TrieNode 객체를 생성하여 해당 문자를 나타내는 자식 노드로 추가한 뒤, 현재 노드를 해당 자식 노드로 변경해줘요.

그리고 단어의 마지막 문자에 해당하는 노드는 isEndOfWord 값을 true로 설정해주죠.

  search(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      let ch = word.charAt(i);
      let node = current.children[ch];
      if (!node) {
        return false;
      }
      current = node;
    }
    return current.isEndOfWord;
  }
}

search() 메소드는 Trie tree에서 단어를 검색하는 메소드에요. 먼저, 현재 노드를 루트 노드로 초기화하고, 단어의 각 문자를 순회하며 해당 문자를 나타내는 자식 노드가 있는지 검사하죠.

만약 해당 자식 노드가 없다면 해당 단어가 Trie tree에 없는 것이므로 false를 반환하고, 단어의 마지막 문자에 해당하는 노드에서는 isEndOfWord 값을 반환해줘요.

이렇게 구현된 Trie tree는 문자열 검색을 효율적으로 수행할 수 있어요.

예를 들어, Trie tree에 "apple", "orange", "banana" 단어가 추가되어 있다면, search("apple")은 true를 반환하고,

search("grape")는 false를 반환하죠.