Trie

Trie란?

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조이다. 래딕스 트리(radix tree), 접두사 트리(prefix tree), 탐색 트리(retrieval tree)라고도 불린다. 트라이(Trie)는 retrieval tree에서 나온 단어이다. 탐색은 dfs 방식으로 탐색한다.

트라이의 장단점

트라이가 무엇인지 알아봤으니, 장단점에 대해 알아보자.

장점

이름처럼 탐색, 즉 문자열 검색을 빠르게 한다. 문자열 탐색을 할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다. 트라이를 이용할 경우 O(m) 여기서 m이란 문자열의 길이를 말한다.

단점

각 노드에 자식들에 대한 주소를 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다 즉, 메모리 측에선 비효율적일 수 있다.

트라이 구현해보기

"apple", "app", "best", "bear"를 트라이에 저장해보자. 다음과 같은 구조로 저장될 것이다.

구조

입력

트라이에 넣으려면 데이터를 입력하는 방식은 다음과 같다.

1. 첫번째 알파벳을 키값으로 하는 노드가 head의 자식중에 있는지 확인한다.
2. 있다면 다음 단계로 넘어간다.
   1. 없다면 새로운 노드를 생성해주고 키값을 첫 번째 글자로 지정해준 후 head의 자식 노드에 추가 해준다.
3. 해당 노드의 자식 노드들 중에 다음 글자가 있는지 확인 후 있다면 다음 단계
   1. 없다면 새로운 노드를 생성해주고 키값을 첫 번째 글자로 지정해준 후 해당 노드의 자식 노드에 추가 해준다.
4. 모든 알파벳을 3번과정을 반복하고 맨 마지막 노드에 data값으로 입력받은 문자열을 넣어준다.

재귀 방식으로 구현해보자.

먼저 Node 클래스를 만들어주자.

class Node{
	private Character key;
    private String data;
    Set<Node> children = new HashSet<>();
    
    public Node(Character key, String data){
    	this.key = key;
        this.data = data;
    }
    
    // 마지막 노드인지 알기 위해
    public boolean isLastWord(){
    	return children.isEmpty();
    }
    
    public Character getKey() {
    	return key;
    }
    public void setData(String data){
    	this.data = data;
    }
    
    public String getData(){
    	return data;
    }
    
    public Set<Node> getChildren(){
    	return children;
    }
}

이 노드를 사용할 Trie 클래스도 만들어주자.

class Trie {
	Node head = null;
    
    public void insert(String input){
    	if(head == null) {
        	head = new Node(null, null);
        }
        
    	insert(head, input, 0);
    }
    
    private void insert(Node node, String input, int index){
    	// 종료 조건
        if(index == input.length()){
        	node.setData(input);
            return;
        }
        
        char c = input.charAt(index);
        Node find = findNodeByKey(node.getChildren(), c);
        
        if(find == null){
        	// 해당 키를 가진 자식이 없으면 새로 생성해서 넣어준다.
            find = new Node(c, null);
            node.getChildren().add(find);
        }
        
        insert(find, word, index + 1);
    }
    
    // 자식 노드에 key값을 가지고있는 노드 찾는 메서드
    private Node findNodeByKey(Set<Node> nodes, char key) {
         for (Node node : nodes) {
            if (node.getKey() == key) {
                return node;
            }
        }
        
        return null;
    }
}

아무것도 없는 헤드에 app을 넣는다고 생각해보자.

처음 헤드에는 아무것도 없으니 a를 넣고, a의 자식중에 p가 없으니 p도 생성해서 넣어주고 p의 자식에 p가 없으니 p를 생성해서 넣어준다.

맨 마지막 p노드의 data에는 "app"이 들어갈 것이다. 이제 apple 도 한 번 넣어보자.

헤드에서 a인(a를 키값으로 가진) 노드가 있으니 a로 이동하고 그 다음 p를 가진 노드가 있는지 확인 후 p로 이동 그 다음 p를 가진 노드가 있는지 확인 후 p로 이동 그 다음 알파벳인 l을 확인 해보자 l을 가진 노드가 자식노드에 없다. 그러니 생성 후 해당 노드로 이동해준다. 마지막 알파벳인 e노드가 l의 자식노드엔 없다. 그러니 또 생성 후 e를 l의 자식노드에 넣어준다. 최종적으로 e노드에 data에 "apple"이 들어간다.

삭제

트라이의 삭제는 생각을 해봐야 될 점이 있다.

1. 해당 노드를 누군가 사용중인 경우

2. 리프 노드가 아닌 경우(자식 노드가 있는 경우)

best를 지운다고 b,e,s,t노드들을 다 지워버리면 bear에 문제가 생긴다. 즉, t 노드와 s노드만 지워야 한다. 만약 app을 지운다고 생각해보자. app노드 들을 다 지워버리면 apple과 append에 문제가 생긴다. 이러면 그냥 app의 data를 null로 바꿔주면 해결된다.

코드로 구현해보자.

public boolean delete(String input) {
	return delete(head, input, 0);
}

 public boolean delete(Node node, String input, int index){
    if(index == input.length()) {
        node.setData(null);
        return node.isLastWord() && node.getData() == null;
    }
    
    char c = word.charAt(index);
    Node find = findNodeByKey(node.getChildren(), c);
    if(find == null) {
        return false;
    }
    
    boolean canDelete = delete(find, input, index + 1);
    if(canDelete) {
        node.children.remove(find);
        // 리프노드가 아니고
        // node에 데이터가 있지 않아야 삭제
        return node.isLastWord() && node.getData() == null;
    }
    return false;
}

검색

검색은 입력과 비슷하다.

public boolean contains(String input) {
    return contains(head, input, 0);
}

private boolean contains(Node node, String input, int index) {
    if(index == input.length()) {
        return node.getData() != null;
    }
    char c = word.charAt(index);
    Node find = findNodeByKey(node.getChildren(), c);
    if (find == null) {
        return false;
    }
    return contains(find, input, index + 1);
}