[자료구조] 트라이(Trie) - Java로 구현하는 2가지 방식

지난번에 트라이를 공부하고 포스팅으로 정리했는데, 아래 포스팅에서는 Map Interface로 구현을 했었습니다.

그런데 백준 - 전설(19585)을 트라이 자료구조로 풀어도 시간 초과가 나길래 더 찾아보니 Array로 구현하는 방식도 있어서 이번에는 Array 방식으로 구현한 트라이도 추가했습니다.

---

트라이(Trie)란?

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조로, 자세한건 지난번 포스팅을 참고해주세요.

[자료구조] 트라이(Trie)

 

트라이(Trie) 구현 방식

트라이(Trie)는 두 가지 방식으로 구현할 수 있습니다.

1. Array를 이용하여 구현
2. Map Interface를 이용하여 구현

Array로 구현할 경우, 빠른 저장과 탐색을 할 수 있다는 장점이 있지만 필요한 메모리의 크기가 너무 크다는 것이 단점입니다.

Map Interface로 구현할 경우, 메모리를 동적으로 할당하여 필요 노드만 메모리를 할당할 수 있다는 장점이 있지만 메모리 제한이 있는 경우 최적화 작업이 꽤 까다롭다는 단점이 있습니다.

 

1. Array로 구현

Array로 구현할 경우, Trie의 Node별 자식 노드를 Node형 배열로 구현합니다. 

이때, Trie Node에 들어가는 단어는 영어 소문자만 있다고 가정하며, 각 노드는 영어 소문자를 정수형(int)으로 변환하여 인덱스로 사용합니다.

 

* 자세한 설명은 이전 포스팅을 참고해주세요.

[자료구조] 트라이(Trie)

 

Node 클래스 생성

Map으로 구현한 Trie 의 Node와 다르게 자식 노드를 Node[] 로 초기화합니다.

childNode의 인덱스에 영어 소문자를 정수형(int)로 변환한 값이 들어가게 됩니다.

그리고 자식 노드의 수(childCnt)와 해당 노드의 문자(val)도 저장해줍니다.

static final int SIZE = 26; // 영어 소문자는 26자
private class Node {
    Node[] childNode = new Node[SIZE]; // 자식 노드: 영어 소문자를 인덱스화 하여 저장
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
    int childCnt = 0; // 자식 노드 수
    char val; // 노드의 문자
}

 

트라이(Trie) 자료구조 클래스 생성

public class TrieArray {
    private Node rootNode;
    public TrieArray() {
    	rootNode = new Node();
    }
}

기본 메서드

1) 노드 추가(insert)

문자열의 문자를 순회하면서 해당 문자가 자식노드로 있는지 확인하여 노드를 추가하는 메서드입니다. 

Map으로 구현했을때와는 다르게 현 노드의 자식 노드가 null 이 아닌지, 즉, 생성되어있는지를 확인하여, 없다면 생성합니다. 

생성시에는 자식 노드를 추가하고, 자식 노드의 문자를 할당해주고, 현 노드의 자식 노드 수를 증가시킵니다.

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드 확인
    for (int i=0; i < word.length(); i++) {
        char c = word.charAt(i);
        // 단어의 특정 문자를 인덱스(int)로 변환
        int intVal = charToInt(c);
        // 현 노드에 인덱스로 변환한 문자가 자식노드로 있는지 확인
        if (node.childNode[intVal] == null) {
            // 자식 노드에 없는 문자라면 새로 생성
            node.childNode[intVal] = new Node();
            node.childNode[intVal].val = c;
            node.childCnt++;
        }
        // 다음 탐색 노드를 자식노드로 변경
        node = node.childNode[intVal];
    }
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

문자열이 트라이에 있는지 확인하는 메서드로, 배열 방식에 맞게 구현해주면 됩니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        int intVal = charToInt(c); // 문자를 인덱스로 변환
        if (node.childNode[intVal] == null) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode[intVal];
    }
    return node != null && node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 존재하는 문자열을 삭제하는 메서드로, 삭제 조건에 맞춰 배열 방식에 맞게 구현해주면 됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
public void delete(Node node, String word, int idx) {
    // 단어의 마지막인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    } else {
        if (node.childCnt == 0) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    }

    char c = word.charAt(idx); // 현재 확인해야하는 문자
    int intVal = charToInt(c); // 문자를 인덱스로 변환

    Node child = node.childNode[intVal]; // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 삭제되었다면, 현 노드의 자식 노드 수 1 차감
    if (node.childNode[intVal] == null) node.childCnt--;
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childCnt == 0 && !node.endOfWord) node = null;
}

 

🧪 구현 테스트

구현 테스트는 Map 방식과 동일하니, 해당 포스팅을 참고해주세요 :)

 

💡 전체 코드(Array로 구현)는 아래 링크에서 확인해주세요.

Algorithm/src/Trie/TrieArray.java at main · hywnj/Algorithm

 

2. Map Interface로 구현

아래 코드는 Map Interface로 구현한 코드이며, 자세한 설명은 이전 포스팅을 참고해주세요.

[자료구조] 트라이(Trie)

 

 

💡 Trie를 Map, Array로 구현한 코드는 아래 링크에서 확인해주세요.

Algorithm/src/Trie at main · hywnj/Algorithm

 

Reference

[자료구조 | Java] Trie(트라이)