[자료구조] Trie 구현

Trie

문자열을 저장하고, 빠르게 탐색하기 위한 트리 형태의 자료구조이다. 탐색 속도가 매우 빠르다

 

Trie 조건

루트 노드는 항상 비어있다.

루트 노드의 자식은 각 단어의 첫 글자이다.

각 문자열의 마지막 글자는 색이 칠해진다.

 

Trie 삽입 방법

삽입할 문자열의 한 문자씩 루트의 자식부터 탐색을 하며 없으면 추가하고 있으면은 타고 들어가는 것을 반복한다.

그리고 문자열의 마지막 문자가 되면 노드의 마지막 노드라는 것을 표시한다.

 

APPLE, BEAR, BED, CAR, CARD, DADDY를 삽입해보았다.단어의 마지막 글자에는 색칠이 되어있고 BEAR와 BED의 BE까지는 동일하기 떄문에 타고 들어간 것을 볼 수 있다.CAR와 CARD도 CAR까지 동일하기에 타고 들어가서 마지막 글자만 각각 색칠되어있는 것을 볼 수 있다.

---

Trie 코드 구현

public class TrieNode {
//    rebro, replay, hi, high, algo, test

    // 글자를 저장할 수 있는 data 변수
    private Character data;

    // 자식노드가 여러개, 몇개인지 모름
    // 배열, 리스트, 맵
    private Map<Character, TrieNode> childNodes;

    // 단어의 끝인지 아닌지 구분
    private boolean isLast;

    public TrieNode(Character data, boolean isLast) {
        this.data = data;
        this.isLast = isLast;
        this.childNodes = new HashMap<Character, TrieNode>();
    }
    
    // ... Getter, Setter 생략...
}

Trie 삽입 구현

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode(null, false);
    }

    // 단어를 입력받아서 반환하는 건 없는 insert 기능
    public void insert(String word) {
    	// 트라이 탐색을 시작할 현재 노드를 루트로 설정
        TrieNode current = root;
        
        for (int i = 0; i < word.length(); i++) {
        	// 자식 노드에 현재 문자 있으면 자식 노드로 이동
            if(current.getChildNodes().containsKey(word.charAt(i))) {
                current = current.getChildNodes().get(word.charAt(i));
            }
            // 자식 녿드에 현재 문자 없으면 새로운 노드 생성
            else {
                TrieNode newNode = new TrieNode(word.charAt(i), false);
                current.getChildNodes().put(word.charAt(i), newNode);
                current = newNode;
            }
        }
        //현재 노드를 마지막 노드라고 표시
        current.setLast(true);
    }
}