so-devlog
🌙
💡 Algorithm

트라이(Trie) 자료구조

date
Aug 21, 2023
slug
data-structure-trie
author
status
Public
category
💡 Algorithm
tags
자료구조
summary
여러 개의 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
type
Post
thumbnail
2017-11-04_22h02_38.webp
 

Trie

= radix tree = prefix tree = retrieval tree

여러 개의 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
자동완성, 사전검색 등 문자열 탐색에 특화되어 있음

Trie 구조

아래 사진에 that, there, this, does, did 총 5개의 단어가 저장되어 있음
각 단어의 공통된 앞부분(prefix)을 중복되지 않게 저장한다는 특징이 있음
notion image
 

Trie 시간복잡도

트라이의 시간복잡도는 주로 노드의 개수와 트리의 높이에 따라 결정됨
  • 노드 개수 : 저장되는 문자열의 수와 문자열의 길이에 따라 달라짐
  • 높이 : 문자열의 길이에 따라 달라짐

1. 삽입(Insertion) = O(L), (L := 문자열의 길이)

각 문자를 트라이의 노드로 연결하면서 삽입하므로, 시간복잡도는 O(L)

2. 검색(Search) = O(L), (L := 문자열의 길이)

트라이의 높이가 문자열의 길이와 일치하기 때문에, 시간 복잡도는 O(L)

3. 삭제(Deletion) = O(L), (L := 문자열의 길이)

문자열을 탐색하면서 삭제해야 하므로 검색과 동일하게 시간복잡도는 O(L)
 

Trie 구현

Structure

class Trie {
	TrieNode root;
}

class TrieNode {
	TrieNode children[ALPHABETS];
	boolean isEndOfWord;
}
 

Trie

Insert(String word) : 트라이에 단어 추가

  1. root에서 시작
  1. word의 각 알파벳마다
    1. 현재 node가 자식으로 가지고 있으면 그 애로 넘어가기
    2. 아니면 node 만들어서 자식으로 넣고 그 애로 넘어가기
  1. 모든 알파벳 끝 → setEndOfWord
public void insert(String word) {
		// 1. root에서 시작
    TrieNode node = root;

    // 2. 단어의 모든 알파벳에 대하여
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        // 트라이 현재 노드의 자식 중 만약 해당 문자가 있다면 그대로 넘어가고, 없다면 생성
        if(node.children[c-'a'] == null) {
            node.children[c-'a'] = new TrieNode();
        }
        node = node.children[c-'a'];
    }

    // 3. 단어의 끝임을 표시
    node.isEndOfWord = true;
}
 

Search(String word) : 트라이에 단어 있는지 확인

  1. root에서 시작
  1. word의 각 알파벳마다
    1. 현재 node가 자식으로 가지고 있으면 그 애로 넘어가기
    2. 아니면 false 리턴
  1. 마지막 노드가 EndOfWord인지 확인하여 true / false 리턴
public boolean search(String word) {
		// 1. root에서 시작
    TrieNode node = root;

		// 2. 단어의 모든 알파벳에 대하여
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);

        // 트라이 현재 노드의 자식 중 만약 해당 문자가 있다면 그대로 넘어가고, 없다면 false
				if(node.children[c-'a'] == null) {
            return false;
        }
        node = node.children[c-'a'];
    }

    // 3. 마지막 노드가 EndOfWord인지 확인하여 true / false 리턴
    return node.isEndOfWord;
}
 

Delete(String word) : 트라이에서 해당 단어 제거

마지막 글자에서 부모 노드 방향으로 되돌아 오는 과정에서 삭제(콜백 형식으로 구현)
❗
노드 삭제시 주의할 점
  1. 삭제하고자 하는 노드는 자식 노드를 가지고 있지 않아야 합니다.
  1. 삭제를 시작하는 첫 노드의 isEndOfWord==true여야 합니다. 즉, 트라이가 가지고 있는 단어여야 삭제를 시작할 수 있습니다.
  1. 삭제를 진행하는 중간 노드의 isEndOfWord==false여야 합니다.삭제 과정 중에서 isEndOfWord가 true라는 것은 또다른 단어가 있다는 의미이므로 삭제 대상이 아닙니다.
// 특정 단어 지우기
public void delete(String word) {
	delete(this.root, word, 0); // 최초로 delete 던지는 부분
}
	
private void delete(TrieNode thisNode, String word, int index) {
		
	char c = word.charAt(index);
	TrieNode childNode = thisNode.children[c-'a'];

	// 아예 없는 단어인 경우(자식을 찾아 내려갈 수 없는 경우) 에러 출력
	if(childNode == null)
		throw new Error("There is no [" + word + "] in this Trie.");
 
	index++;
  
// 마지막 노드(삭제를 시작하는 첫 노드)에 도달했을 때
  if (index == word.length()) {
      // 삭제조건 2번 항목 확인
      // EndOfWord가 아닌 경우(트라이가 가지고 있는 단어가 아닌 경우) 에러 출력
      if (!childNode.isEndOfWord) throw new Error("There is no [" + word + "] in this Trie.");

      // 삭제조건 1번 항목 확인
      // 자식 노드가 없으면(이 단어를 포함하는 더 긴 단어가 없으면) 노드 삭제
      if (!childNode.hasChild()) {
          thisNode.children[c] = null;
      } else { // 자식 노드가 있다면 이 노드가 단어의 마지막이었다는 것만 false로 변경
          childNode.isEndOfWord = false;
      }
  }

  // 아직 마지막 노드가 아니라면
  else {
      // 콜백 함수
      delete(childNode, word, index);

      // 삭제조건 1,3번 항목
      // 삭제 중, 자식 노드가 없고 현재 노드로 끝나는 다른 단어가 없는 경우 이 노드 삭제
      if (!childNode.isEndOfWord && !childNode.hasChild())
          thisNode.children[c] = null;
  }
}
 

TrieNode

containsKey(char ch) : 노드가 해당 알파벳을 자식으로 가지고 있는지 확인

public boolean containsKey(char ch) {
    if(children[ch-'A'] != null) return true; // 해당 알파벳을 자식 노드로 가지고 있다면 true
    return false;
}

get(char ch) : 노드가 가지고 있는 자식 노드 리턴

public TrieNode get(char ch) {
    return children[ch-'A']; // 해당 알파벳 자식 노드 return, 만일 없다면 null
}

setChildren(char ch, TrieNode node) : 해당 노드를 ch위치의 자식으로 추가

public void setChildren(char ch, TrieNode node) {
    children[ch-'A'] = node;
}

setEndOfWord() : 해당 노드가 단어의 끝임을 표시

public void setEndOfWord() {
   this.isEndOfWord = true;
}

hasChild() : 해당 노드에게 자식이 있는지 판별

public boolean hasChild() {
    for (int i = 0; i < 26; i++) {
        if(children[i] != null) {
            return true;
        }
    }
    return false;
}