트라이(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 유무를 따져 구현합니다