📌 트라이(Trie)란?

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 트라이의 예시로는 일상생활에서 쉽게 접할 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화된 예시들이 있습니다.

래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 합니다. 트라이는 retrieval tree에서 나온 단어입니다.

특징

• 문자열 검색을 빠르게 할 수 있습니다.
• 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적입니다.
• 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다. (메모리 측면에서 비효율적일 수 있습니다.)

시간복잡도

삽입 : 삽입하려는 문자열의 길이 L, O(L)
검색 : 검색하려는 문자열의 길이 L, O(L)
삭제 : 삭제하려는 문자열의 길이 L, O(L)

❗ But, 문자열이 길고 문자 집합이 크다면 공간적으로 많은 자원을 소비할 수 있습니다.

📌 구현

static class Trie {
	boolean end;
    boolean pass;
    Trie[] child;
    
    Trie() {
    	end = false;
        pass = false;
        child = new Trie[10];
    }
    
    public boolean insert(String str, int idx) {
    	//끝나는 단어 있으면 false 종료
    	if(end) return false;
        
        //idx가 str만큼 왔을때
        if(idx == str.length()) {
        	end = true;
            if(pass) return false;
            else return true;
        }
        
        //idx가 str에 오지 않았을 떄
        else {
        	int next = str.charAt(idx) - '0';
            if(child[next] == null) {
            	child[next] = new Trie();
                pass = true;
            }
            return child[next].insert(str, idx + 1);
        }
    }
}

참고

• https://gyoogle.dev/blog/computer-science/data-structure/Trie.html
• https://velog.io/@kimdukbae/자료구조-트라이-Trie

피드백 및 개선점은 댓글을 통해 알려주세요😊