[알고리즘] 트라이 개념 및 구현하기

트라이(Trie)란?

문자열을 저장하고 탐색하기 위한 트리모양 자료구조

특징

  • 자동완성, 사전찾기에 응용됩니다
  • 문자열 탐색에 최적화된 자료구조 입니다
  • 문자마다 노드를 만들어야하기 때문에 저장공간이 많이 필요합니다
  • 탐색 시간복잡도는 문자열의 길이 L에 대해 O(L)만큼만 걸립니다

규칙

트라이를 구현할 때 몇가지 규칙이 있습니다.

  1. root 노드는 항상 비어있습니다
  2. 간선은 추가될 문자입니다
  3. 각 노드는 이전 정점의 값 + 간선에 추가될 문자를 값으로 가집니다
  4. 해시테이블을 사용해 구현할 수 있습니다

구현

자바스크립트로 다음과 같이 구현할 수 있습니다. 먼저 각 문자를 표현할 Node 클래스가 필요합니다.

class TrieNode {
  constructor(str = "") {
    this.word = false; // 입력한 단어 그 자체인지
    this.str = str; 
    this.children = {};
  }
}
  • 단어인지 구분하는 word가 있습니다.

Tree라는 단어를 넣으면, 마지막 노드에만 word=True가 됩니다

  • children으로 트라이 자식노드들을 관리합니다

다음은 자바스크립트로 구현한 트라이 자료구조입니다

class Trie {
  constructor() {
    this.root = new TrieNode(); // 루트는 항상 비어있습니다
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!(char in node.children)) { 
        node.children[char] = new TrieNode(node.str + char);
      }
      node = node.children[char];
    }
    node.word = true;
  }

  find(word) {
    let node = this.root;
    for (const char of word) {
      if (char in node.children) {
        node = node.children[char];
      } else {
        return false;
      }
    }
    return node.word;
  }
}

다음은 파이썬으로 구현한 트라이 입니다

class TrieNode:
    def __init__(self,str=""):
        self.word = False
        self.str = str
        self.children = {}

class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()
    
    def insert(self,word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode(node.str+char)
            node = node.children[char]
        node.word = True

    def find(self,word):
        node=self.root
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                return False
        return node.word
  • insert 메서드는 해당 단어의 글자를 하나하나씩 node를 만들어 집어넣는 메서드입니다.

  • find 메서드는 해당 단어가 트라이에 존재하는지 확인하는 메서드입니다.

  • 만약 찾고자 하는 단어 중에 하나의 글자라도 node.children에 존재 하지 않는다면 false를 반환합니다

  • node.children에 존재해서 끝까지 탐색하였더라도 해당 노드가 word=false라면 존재하지 않는 단어입니다. 다음 예시를 들 수 있습니다

const trie = new Trie();
trie.insert("가");
trie.insert("나");
trie.insert("다");
trie.insert("가나다");

trie.find("가나") // false
  • 가나 단어는 모두 트라이에 존재하는 단어이지만, 해당 가나 노드가 입력된 단어가 아니기 때문에 word=false입니다

정리

  1. 트라이는 문자열을 저장, 탐색하는데 안성맞춤인 알고리즘입니다. 특히 탐색 시간복잡도는 문자열의 길이 O(L)만큼만 듭니다.

  2. insert() find()메서드는 단어의 문자를 하나씩 확인하면서 해당 node의 childrend 유무를 따져 구현합니다

좋은 웹페이지 즐겨찾기