Portfolio

Trie

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조

"ant"를 추가하기 위하여 root의 자식노드 'a'가 존재하지 않으면 추가하고 동일한 방법으로 'n', 't' 추가

"ant"를 탐색하기 위하여 root -> 'a' -> 'n' -> 't' 3번의 이동으로 탐색 가능

Java로 구현

TrieNode


public class TrieNode {

    private Map<Character, TrieNode> childNodes = new HashMap<>();

    private boolean isLastChar;

    public Map<Character, TrieNode> getChildNodes() {
        return childNodes;
    }

    public boolean isLastChar() {
        return isLastChar;
    }

    public void setIsLastChar(boolean isLastChar) {
        this.isLastChar = isLastChar;
    }
}

Trie


public class Trie {

    private TrieNode rootNode;

    public Trie() {
        rootNode = new TrieNode();
    }

    void insert(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); i++) {
            node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
        }
        node.setIsLastChar(true);
    }

    boolean contains(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); i++) {
            char charAtIdx = word.charAt(i);
            node = node.getChildNodes().get(charAtIdx);

            if (node == null) {
                return false;
            }
        }

        return node.isLastChar();
    }

    void delete(String word) {
        delete(this.rootNode, word, 0);
    }

    private void delete(TrieNode node, String word, int index) {
        char charAtIdx = word.charAt(index);
        TrieNode childNode = node.getChildNodes().get(charAtIdx);
        if(childNode == null) {
            System.out.println("There is no \\"" + word + "\\" in this Trie.");
            return;
        }

        index++;
        if (index == word.length()) {
            if (!childNode.isLastChar()) {
                System.out.println("There is no \\"" + word + "\\" in this Trie.");
                return;
            }

            if (!childNode.getChildNodes().isEmpty()) {
                childNode.setIsLastChar(false);
            } else {
                node.getChildNodes().remove(charAtIdx);
            }
        } else {
            delete(childNode, word, index);

            if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty()) {
                node.getChildNodes().remove(charAtIdx);
            }
        }
    }

    void print() {
        Queue<Map<Character, TrieNode>> queue = new LinkedList<>();
        queue.add(rootNode.getChildNodes());

        while (!queue.isEmpty()) {
            for (Map.Entry<Character, TrieNode> entry : queue.poll().entrySet()) {
                System.out.println(entry.getKey());
                queue.add(entry.getValue().getChildNodes());
            }
        }
    }
}