Trie 자료 구조 알고리즘 만들기

알고리즘 문제를 풀다보면 문자열을 다루고 원하는 문자열을 검색하는 문제를 만날때가 종종 있다.

그때마다 Trie 자료 구조에 대해 찾아보곤 하는데 매번 까먹어서 잊지 않을려고 직접 기록해본다.

우선 Trie의 개념에 대해 이야기 해보겠다.

Trie 자료 구조의 개념

Trie는 트리 형태의 자료 구조로 문자열을 빠르게 저장하고 검색하기 위해 사용되는데 사용한다.

개념을 이해하는 것은 어렵지 않았지만 막상 코드를 작성하면서 내가 대충 이해하고 넘어갔구나 생각하게 됬다.

static class Trie{
	boolean isLast = false;
    	//현재 노드의 자식 노드 배열을 만든다. 
    	//배열의 크기는 영어 소문자를 기준으로 26개.
    	Trie[] childNodes = new Trie[26]
}

기본적으로 Trie 클래스가 가지는 변수들을 선언해줬다.

isLast변수를 통해 현재 노드가 마지막 문자인지 아닌지를 나타낼 수 있다.

childNodes 배열을 통해 현재 노드가 가지는 다음 노드들의 배열을 저장 할 수 있도록 한다.

두가지 사용은 문자열 삽입에서 자세히 다루도록 하겠다.

아래의 코드는 삽입 메소드 이다.

public void insert(int index, String str) {
	char c = str.charAt(index);
    	int askii = c-'a';
	if(childNodes[askii] == null) {
		childNodes[askii] = new Trie();
	}
	if(index == str.length()-1) {
		this.isLast = true;
		return ;
	}
	childNodes[askii].insert(index+1, str);
}

|코드 설명|

우선 나는 insert 메소드를 사용할 때 재귀 방식을 사용하는데 문자열을 잘라서 넘기기 싫기 때문에 인덱스 번호를 함께 넘겼다.

우선 현재 문자가 노드 배열에 없다면 새로운 노드를 배열에 삽입하게 한다.

혹은 있다면 새로 생성하지 않고 넘어간다. 이때 해당 인덱스의 노드에 insert함수를 사용하도록 한다.

재귀방식을 이용하여 해당 노드 다음 자식 노드들이 생겨난다.

만약 index가 문자열을 마지막이라면 현재 노드의 isLast값에 true를 삽입하고 재귀에서 벗어나면서 마무리 된다.

public boolean find(int index, String str) {
	char c = str.charAt(index);
	int askii = c - 'a';
	if(childNodes[askii] == null) return false;
    	if(this.isLast && (index == str.length()-1)) return true;
	return childNodes[askii].find(index+1, str);
}

|코드 설명|

위의 코드는 문자열을 찾는 코드이다.

위의 코드와 마찬가지로 재귀 방식을 사용하여 현재 노드의 find를 사용하여 다음 인덱스 번호화 문자열을 넘겨준다.

만약 문자열 노드가 없다면 false값을 리턴하여 없음을 알리고, 만약 있을 때 문자가 현재 문자열을 마지막 문자이고 isLast가 true인 상태라면 true을 리턴하여 문자열이 있음을 알린다.

| 모든 코드 |

import java.util.*;
public class TrieAlgorithmPractice {
	public static void main(String[] args) {
		Trie t = new Trie();
		t.insert(0, "find");
		t.insert(0, "egg");
		t.insert(0, "east");
		t.insert(0, "finded");
		t.insert(0, "to");
		t.insert(0, "ten");
		System.out.println("find is"+t.find(0, "find"));
		System.out.println("find is"+t.find(0, "finde"));
		System.out.println("find is"+t.find(0, "eggs"));
		System.out.println("find is"+t.find(0, "ted"));
		System.out.println("find is"+t.find(0, "to"));
		System.out.println("find is"+t.find(0, "too"));
	}
	
	static class Trie{
		boolean isLast = false;
		Trie[] childNodes = new Trie[26];
		
		public void insert(int index, String str) {
			char c = str.charAt(index);
			int askii = c-'a';
			if(childNodes[askii] == null) {
				childNodes[askii] = new Trie();
			}
			if(index == str.length()-1) {
				this.isLast = true;
				return ;
			}
			childNodes[askii].insert(index+1, str);
		}
		
		public boolean find(int index, String str) {
			char c = str.charAt(index);
			int askii = c - 'a';
			if(childNodes[askii] == null) return false;
			if(index == str.length()-1) {
				if(this.isLast) return true;
				else return false;
			}
			return childNodes[askii].find(index+1, str);
		}
	}

}

| 결과 |