[자료구조] Trie 트라이

트라이 (Trie)

• retrieval Tree에서 온 단어
• 문자열들을 트리 구조로 저장하여 O(log n) 속도로 빠르게 문자열을 탐색할 수 있게 해준다.
• 알고리즘 문제에선 주로 문자열의 '접두어', '~로 시작하는', '접미어', '~로 끝나는' 등의 키워드가 나오는 접두어, 접미어 판별 문제에서 사용된다. 

 

 

※ 참조 문제

코딩테스트 연습 - 가사 검색

 

자바로 트라이 구현하기

1. 노드 (Node) 클래스

import java.util.HashMap;

public class Node {

    //해당 node 밑의 서브트리 총 node 개수 (옵션 : 즉 필요에 따라 넣는 요소)
    int count = 0;

    // isLast = true면 해당 문자열 존재
    boolean isLast = false;

    //자식 노드들
    HashMap<Character, Node> childNodes = new HashMap<>();

    public Node()
    {

    }

}

 

속성	설명
count	- 해당 문자 노드 밑에 있는 서브트리의 총 노드 개수이다. - 옵션 속성 EX) 'app' 으로 시작하는 문자열이 총 50개 저장되어 있다면 app에서 마지막 'p' 노드의 count는 50이 된다.
childNodes	- 자식노드들로 Character 를 key값으로 가진다.
isLast	- 해당 문자까지의 문자열이 존재하는 지 표시해준다. EX) 'app', 'apple' 이라는 문자열이 둘다 저장되었을 때, isLast 변수가 없다면 app은 apple로 가는 도중에 있기 때문에 app이라는 문자열이 존재하는지 확인 할 수 없다.

 

2. 트라이 (Trie) 클래스

import java.util.HashMap;

public class Trie {

    Node root = new Node();

    public Trie()
    {

    }

//모든 메서드는 옵션이다.
    //삽입
    public void insert(String str)
    {
        Node node = root;

        for(int i = 0;i<str.length();i++)
        {
            char c = str.charAt(i);
            node.count++;

            node.childNodes.putIfAbsent(c, new Node());
            node = node.childNodes.get(c);
            //마지막 문자면 isLast = true
            if(i == str.length() - 1)
            {
                node.isLast = true;
                return;
            }
        }
    }

    //조회
    public boolean search(String str)
    {
        Node node = root;

        for(int i = 0;i<str.length();i++)
        {
            char c = str.charAt(i);

            //문자 있으면 이동
            if(node.childNodes.containsKey(c))
                node = node.childNodes.get(c);
            //없으면 false 리턴
            else
                return false;

            //마지막 문자면 문자열 존재하는지 확인(isLast = true)
            if(i == str.length()-1)
            {
                if(!node.isLast)
                    return false;
            }
        }
        return true;
    }

    //삭제
    public void delete(String str)
    {
        Node node = root;

        for(int i = 0;i<str.length();i++)
        {
            char c = str.charAt(i);

            node.count--;

            if(i < str.length()-1)
                node = node.childNodes.get(c);
            else
            {
                Node child = node.childNodes.get(c);

                if(child.childNodes.isEmpty())
                    node.childNodes.remove(c);
                else
                    child.isLast = false;
            }
        }
    }
}

 

메서드	설명
insert	- 문자열 삽입 메서드 - 추가 할 때마다 node의 count는 1씩 증가
search	- 문자열 조회 메서드 - 찾고 있는 문자열의 마지막 문자 노드의 isLast가 true라면 해당 문자열이 존재하는 것이다.
delete	- 문자열 삭제 메서드 - 마지막 문자 노드의 childNodes가 비었으면 바로 부모 노드에서 삭제 - childNodes가 존재한다면 isLast만 false로 바꾸어준다.