[자료구조] 트라이

트라이 (Trie)

 

• 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조
• 문자열 저장을 위한 메모리가 필요하지만 탐색이 so fast
• 정렬된 트리 구조

 

 

class Node {
    HashMap<Character, Node> child;
    boolean isTerminal;

    public Node(){
        this.child = new HashMap<>();
        this.isTerminal = false;
    }
}

 

 

 

1. 삽입

 

public void insert(String str) {
    Node cur = this.root;

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

        if (!cur.child.containsKey(c)) { // key가 없으면
            cur.child.put(c, new Node()); // 새 노드 넣기
        }

        cur = cur.child.get(c);

        if (i == str.length() - 1) {
            cur.isTerminal = true;
            return;
        }

    }
}

 

 

2. 탐색

 

public boolean search(String str) {
    Node cur = this.root;

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

        if (cur.child.containsKey(c)) {
            cur = cur.child.get(c);
        } else {
            return false;
        }

        if (i == str.length() - 1) {
            if (!cur.isTerminal) {
                return false;
            }
        }

    }
    return true;
}

 

 

3. 삭제

 

public void delete(String str) {
    boolean ret = this.delete(this.root, str, 0);
    if (ret) {
        System.out.println("삭제 완료");
    } else {
        System.out.println("존재하지 않는 단어");
    }

}

public boolean delete(Node node, String str, int idx) {
    char c = str.charAt(idx);

    if(!node.child.containsKey(c)) {
        return false;
    }

    Node cur = node.child.get(c);
    idx++;

    if (idx == str.length()) {
        if (!cur.isTerminal) {
            return false;
        }

        cur.isTerminal = false;

        if (cur.child.isEmpty()) {
            node.child.remove(c);
        }
    } else {
        if (!this.delete(cur, str, idx)) { // false면
            return false;
        }

        if (!cur.isTerminal && cur.child.isEmpty()) {
            node.child.remove(c);
        }

    }

    return true;
}