트라이, 그림으로 쉽게 이해하기

1. 트라이란?

트라이는 트리의 일종으로서 대량의 문자열을 빠른 시간 안에 삽입, 삭제, 조회 하기 위해 고안된 알고리즘이다.

2. 트라이의 원리

'선두의 문자가 같은 녀석들끼리 최대한 같은 가지에 밀어 넣는다.'

• 1️⃣ 노드 하나 = 문자 하나, 수직적으로 문자열의 문자를 하나씩 저장함
• 2️⃣ A의 길이 < B의 길이 인데, $A\subset{B}$ 인 경우, A와 B는 직계존속 (A = 부모 노드, B = 자식 노드)
• 3️⃣ $A\nsubseteq{B}$ 인데, 둘이 같은 선두 문자를 가질 때, A와 B는 방계임 (형제 관계 이거나, 삼촌-조카 관계)

이를 기초로 한 트라이의 한 형태이다. 해당 트라이에 넣은 문자열은 다음과 같다.
["frodo", "front", "frost", "frozen", "frame", "bus", "busy"]

3. 트라이의 구조

• 1️⃣ ROOT 노드는 항상 비어있다. (ROOT 노드는 시작점, ROOT의 자식들이 어떤 단어의 시작점 이다.)
• 2️⃣ 하나의 노드는 다음 문자 노드를 가리키는 Map과 현 노드가 문자열의 끝인지를 나타내는 boolean 값으로 이루어져 있다.

class Node {
    HashMap<Character, Node> children; 
    boolean isEnd;
}

여기선 각각을 children 과 isEnd라고 하겠다.
children의 Key는 다음 문자 (자식 노드)의 이름이고, Value는 그것의 객체 주소를 나타낸다. 예를 들어, 위의 트리에서 현재 보고 있는 노드가 fro에서 o 일 때 children의 구성 요소는 다음과 같다.

[<d, #fdfd31>, <n, #dfd123>, <s, #dfkp30>, <z, #dpfskd>]

isEnd는 왜 필요할까? 그 이유는, 위의 bus와 busy 처럼 하나의 단어 전체가 다른 단어의 선두가 되는 경우가 존재하기 때문이다. 따라서 bus의 s에 isEnd 표시를 해두어서 bus 라는 단어가 트라이에 저장된 상태임을 표시해두어야 한다. 위 그림에서 파란색으로 색칠된 노드가 바로 isEnd가 true인 노드 들이다.

4. 트라이의 복잡도

(1) 시간 복잡도

삽입, 삭제, 조회 하려는 문자열의 길이를 $L$이라 했을 때,
삽입, 삭제, 조회 시간 복잡도: $O(L)$

이유: 위에서 보았다시피, 트라이는 겹치는 단어가 많은 문자들을 최대한 같은 가지에 밀어넣는다. 따라서 하나의 문자열은 무조건 하나의 경로에만 존재한다. 따라서
조회 시 최악의 경우, 찾으려는 문자열의 모든 문자만큼 트리의 노드를 수직으로 조회 하므로 $O(L)$,
삽입 시에도 마찬가지로 모든 문자를 트리에 수직적으로 저장하므로 $O(L)$
삭제 시에도 문자열의 끝 부분까지 도달해야 하므로 $O(L)$ 의 시간이 든다.

(2) 공간 복잡도

트리의 깊이를 $h$ 라고 했을 때, 공간복잡도: $O(26^{h})$

알고리즘은 항상 연금술사처럼 등가교환의 법칙이 성립한다. 위처럼 시간복잡도가 빠를 수록, 공간복잡도를 많이 소모한다. 트라이도 마찬가지 이다.

최악의 경우, 모든 노드가 26가지 자식 노드를 가져야 한다. 따라서 트리의 높이를 h라고 할 때, $O(26^{h})$ 의 공간 복잡도가 든다. 객체 하나가 평균 28byte인 걸 감안하면, 꽤 많은 공간이 필요하다. 예를 들어 h = 5라고 하자. 그러면 총 332678528 byte가 필요하고, MB로 환산하면, 332MB가 든다.

5. 트라이 구현

생성자, 삽입, 조회, 삭제 순으로 하나씩 구현해보겠다.

(1) 생성자

트라이의 구성요소가 되는 Node와 트라이의 구현체인 Tri는 가독성을 위해서 클래스를 따로 만들겠다.

Node✨

class Node {
    HashMap<Character, Node> children; 
    boolean isEnd;

    public Node () {
        this.children = new HashMap<>();
        this.isEnd = false;
    }
}

Tri✨

class Tri {
    Node root; 

    public Tri () {
        this.root = new Node();
    }
}

만약 Tri의 객체를 하나 선언했다면, 다음과 같이 만들어질 것이다.

이제 Root에 새로운 문자열이 들어올 때마다, children에 새로운 객체가 만들어질 것이다.

(2) 삽입

삽입은 다음 순서대로 이루어진다.

• 1️⃣ Root 노드를 방문하여, 그것의 children을 확인한다.
• 2️⃣ 만약 현재 집어넣어야할 문자(이하 A)가 children에 있다면, 아무 행동을 하지 않는다.
• 3️⃣ 만약 A가 children에 없다면, 새롭게 객체 생성 후, children에 삽입한다. <삽입할 문자, 객체>
• 4️⃣ 이제 A의 객체를 방문하고, 2️⃣~3️⃣을 문자열 전부 트라이에 집어넣을 때까지 반복한다.
• 5️⃣ 문자열의 끝 문자를 노드에 삽입했다면, 해당 노드의 isEnd = true로 바꿔준다.

자식노드를 끊임없이 방문하긴 하지만, 다시 원래 노드로 되돌아와서 하는 계산이 없는 단방향 움직임이므로, 재귀가 아닌 반복문으로 구현해도 된다. (필자는 이 편이 가독성이 높아 그렇게 진행했다. )

    public void insert(String str) {
        Node cur = this.root;   // 초기화
        for (int i = 0; i < str.length(); i++) {
            char now = str.charAt(i);                    // 현재 tri에 삽입해야할 문자
            cur.children.putIfAbsent(now, new Node());
            cur = cur.children.get(now);
        }
        cur.isEnd = true;
    }

cur 노드에 계속 자식 노드가 할당되며, 트라이를 깊게 탐구한다. 여기서 헷갈리지 말아야 할 점이, 현재 넣어야할 문자 now는 현재 확인 중인 Node cur의 자식노드들을 가리키는 children에 삽입된다는 것이다. 그 이유는 우리가 처음에 값이 비어있는 Root 노드 부터 시작하고, 그것의 자식노드에 문자열의 첫 문자를 넣도록 설계했기 때문이다.

ex ✨

위 트라이에 "best" 삽입

a. b 넣으려 봤는데 이미 root의 children에 존재함, 그래서 cur = 노드 b로 이동만 한다.

b. e 넣으려고 봤는데, b의 children에는 존재하지 않는다. e 삽입

c. e의 children에는 s가 존재하지 않는다. s 객체 생성 후 삽입

d. s의 children에는 t가 존재하지 않는다. t 객체 생성 후 삽입

e. t가 문자열의 끝임으로 isEnd = true로 바꿔준다.

(3) 조회

조회는 삽입과 매커니즘이 비슷하다.

• 1️⃣ Root 노드부터 문자열의 문자를 하나씩 조회한다. (여기서 조회란, 해당 Node의 Children에 현재 조회 중인 문자가 존재하는지 이다.)
• 2️⃣ 만약 조회해도, 현 조회 중인 문자가 children에서 나오지 않으면, 해당 문자열은 트라이에 저장되지 않았다는 의미이므로, 함수를 종료하고 false를 반환한다.
• 3️⃣ 만약 문자열의 끝 문자 노드를 조회했는데, isEnd = false라면, 해당 문자열이 트라이에 저장되지 않았다는 의미이므로, 함수를 종료하고 false 를 반환한다.
• 4️⃣ 위 2️⃣, 3️⃣ 에 해당하지 않고, 함수를 무사히 마치면 true를 반환한다.

public boolean search(String str) {
    Node cur = this.root;
    for (int i = 0; i < str.length(); i++) {
        char now = str.charAt(i);
        if(!cur.children.containsKey(now)) return false;
        cur = cur.children.get(now);
    }
    return cur.isEnd;
}

ex ✨

a. 시작 문자인 b가 root의 자식 노드로 존재하는가? YES

b. e가 b의 자식노드로 존재하는가? YES

c. s가 e의 자식노드로 존재하는가? YES

d. t가 s의 자식노드로 존재하는가? YES

e. t 노드의 isEnd = true인가? YES

(4) 삭제

삭제의 경우, 신경 써줘야 할 것이 여러가지가 있다.

• 1️⃣ 조회와 같이 현재 보고 있는 문자열의 끝까지 내려간다. (이때, 조회 트라이 내에서 문자열의 일부가 없는게 확인되면 바로 false 반환)
• 2️⃣ 현재 끝문자의 노드를 b라고 하자.
  • 2️⃣ - 1) 만약 b의 isEnd = false이면 삭제하고자 하는 문자열은 트라이 내부에 존재하지 않는다는 의미이므로 false를 반환한다.
  • 2️⃣ - 2) 만약 b에게 자식 노드가 존재하지 않는다면, 부모노드의 children에서 b를 삭제한다.
  • 2️⃣ - 3) 자식노드가 존재한다면 isEnd = true로 바꾸고, 부모 노드로 다시 돌아간다. (재귀 이용)
• 3️⃣ 이제 b의 부모노드가 새로운 b가 될 것이다. 위의 2️⃣ 번을 모든 문자열에 대해 시행한다.

isEnd = true로 바꾼다의 의미는 이제 입력으로 받은 현 문자열이 트라이 내에 존재하지 않는다는 것을 명시하는 것이다. 위의 삽입과 조회는 트리 내에서 단방향 이동만 구현하면 되어서 반복문으로 쉽게 구현했으나, 이제는 끝까지 가서 되돌아올 때 작업을 해야 하므로, 재귀를 사용해야 한다.

    public boolean delete(String str) {
        return delete(this.root, str,0);
    }

    private boolean delete(Node cur, String str, int idx) {
        char now = str.charAt(idx);                         // 현재 지울값
        if(!cur.children.containsKey(now)) return false;    // 이 값을 가지고 있지 않으면 false 반환
        Node child = cur.children.get(now);                 // 현재 지울값을 가리키는 객체로 이동
        idx++;                                              // 다음 지울 값을 보기 위함

        if(idx == str.length()){                            // 현재 문자가 문자열의 끝이면
            if(!child.isEnd) return false;                  // 근데 트라이 트리 내에서는 끝이라 표시 되어 있지 않으면, delete 계산 전부터 뭔가 잘못된 것: false 반환
            child.isEnd = false;                            // 끝이라 표시 되어 있다면, 이제 더이상 해당 값을 끝으로 가지는 문자는 없음으로, false로 전환
            if(child.children.isEmpty()) cur.children.remove(now);  // 트라이 내에서도 해당 문자가 끝 노드 이면, 해당 노드를 지워버림

        }else {                                                     // 현재 보는 문자가 지우려는 문자열의 끝이 아니면
            if (!this.delete(child, str, idx)) return false;        // 다음 문자를 조회하여 삭제 여부를 따짐 (재귀) => 근데 삭제 되지 않으면 delete가 안된다는 소리임 false 반환
            if (!child.isEnd && child.children.isEmpty()) cur.children.remove(now); // 이전꺼 다 삭제했고, 현재 노드가 어떤 문자의 끝이 아니며, 뒤로 문자열이 비어 있다면 삭제한다.
        }
        return true;
    }

(5) 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

    }
}

class Tri {
    Node root;

    public Tri () {
        root = new Node();
    }

    public void insert(String str) {
        Node cur = this.root;   // 초기화
        for (int i = 0; i < str.length(); i++) {
            char now = str.charAt(i);
            cur.children.putIfAbsent(now, new Node());
            cur = cur.children.get(now);
        }
        cur.isEnd = true;
    }

    public boolean search(String str) {
        Node cur = this.root;
        for (int i = 0; i < str.length(); i++) {
            char now = str.charAt(i);
            if(!cur.children.containsKey(now)) return false;
            cur = cur.children.get(now);
        }
        return cur.isEnd;
    }

    public boolean delete(String str) {
        return delete(this.root, str,0);
    }

    private boolean delete(Node cur, String str, int idx) {
        char now = str.charAt(idx);                         // 현재 지울값
        if(!cur.children.containsKey(now)) return false;    // 이 값을 가지고 있지 않으면 false 반환
        Node child = cur.children.get(now);                 // 현재 지울값을 가리키는 객체로 이동
        idx++;                                              // 다음 지울 값을 보기 위함

        if(idx == str.length()){                            // 현재 문자가 문자열의 끝이면
            if(!child.isEnd) return false;                  // 근데 트라이 트리 내에서는 끝이라 표시 되어 있지 않으면, delete 계산 전부터 뭔가 잘못된 것: false 반환
            child.isEnd = false;                            // 끝이라 표시 되어 있다면, 이제 더이상 해당 값을 끝으로 가지는 문자는 없음으로, false로 전환
            if(child.children.isEmpty()) cur.children.remove(now);  // 트라이 내에서도 해당 문자가 끝 노드 이면, 해당 노드를 지워버림

        }else {                                                     // 현재 보는 문자가 지우려는 문자열의 끝이 아니면
            if (!this.delete(child, str, idx)) return false;        // 다음 문자를 조회하여 삭제 여부를 따짐 (재귀) => 근데 삭제 되지 않으면 delete가 안된다는 소리임 false 반환
            if (!child.isEnd && child.children.isEmpty()) cur.children.remove(now); // 이전꺼 다 삭제했고, 현재 노드가 어떤 문자의 끝이 아니며, 뒤로 문자열이 비어 있다면 삭제한다.
        }
        return true;
    }

}

class Node {
    HashMap<Character, Node> children;
    boolean isEnd;

    public Node(){
        children = new HashMap<>();
        this.isEnd = false;
    }
}