[数据结构与算法]【恋上数据结构与算法】Trie

持续学习&持续更新中…

Trie

接口设计

public interface Trie<V> {

    int size();

    boolean isEmpty();

    void clear();

    V add(String key, V value); // 添加一个单词

    V remove(String key); // 删除这个单词

    V get(String key); // 拿到这个单词对应的value

    boolean contains(String key); // 判断Trie中是否有这个单词

    boolean startsWith(String prefix); // 判断Trie中是否有以这个单词为前缀的单词

}

实现

TrieMap_v0

public class TrieMap_v0<V> implements Trie<V> {

    private int size;
    private final Node<V> root = new Node<>();

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        root.getChildren().clear();
        size = 0;
    }

    @Override
    public V get(String key) {
        final Node<V> node = node(key);
        return node == null ? null : node.value;
    }

    @Override
    public boolean contains(String key) {
        return node(key) != null;
    }

    @Override
    public boolean startsWith(String prefix) {
        keyCheck(prefix);
        Node<V> node = root;
        for (int i = 0, len = prefix.length(); i < len; i++) {
            char c = prefix.charAt(i);
            Node<V> childNode = node.getChildren().get(c);
            if (childNode == null) return false;
            node = childNode;
        }
        return true;
    }

    @Override
    public V add(String key, V value) {
        keyCheck(key);
        Node<V> node = root;
        for (int i = 0, len = key.length(); i < len; i++) {
            char c = key.charAt(i);
            Node<V> childNode = node.getChildren().get(c);
            if (childNode == null) {
                childNode = new Node<>();
                node.getChildren().put(c, childNode);
            }
            node = childNode;
        }
        if (node.isWord) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        node.isWord = true;
        node.value = value;
        size++;
        return null;
    }

    @Override
    public V remove(String key) {
        return null;
    }

    private Node<V> node(String key) {
        keyCheck(key);
        Node<V> node = root;
        for (int i = 0, len = key.length(); i < len; i++) {
            char c = key.charAt(i);
            Node<V> childNode = node.getChildren().get(c);
            if (childNode == null) return null;
            node = childNode;
        }
        return node.isWord ? node : null;
    }

    private void keyCheck(String key) {
        if (key == null || key.length() == 0) throw new IllegalArgumentException("Key must not be empty!");
    }

    private static class Node<V> {
        HashMap<Character, Node<V>> children;
        V value;
        boolean isWord;

        HashMap<Character, Node<V>> getChildren() {
            if (null == children) children = new HashMap<>();
            return children;
        }
    }

}

TrieMap

public class TrieMap<V> implements Trie<V> {

    private int size;
    private Node<V> root;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    @Override
    public V get(String key) {
        Node<V> node = node(key);
        if (node != null && node.isWord) return node.value;
        return null;
    }

    @Override
    public boolean contains(String key) {
        Node<V> node = node(key);
        return node != null && node.isWord;
    }

    @Override
    public boolean startsWith(String prefix) {
        Node<V> node = node(prefix);
        return node != null;
    }

    @Override
    public V add(String key, V value) {
        keyCheck(key);
        if (null == root) root = new Node<>(null, null);
        Node<V> node = root;
        for (int i = 0, len = key.length(); i < len; i++) {
            char c = key.charAt(i);
            boolean childrenIsEmpty = (node.children == null);
            Node<V> childNode = childrenIsEmpty ? null : node.children.get(c);
            if (childNode == null) {
                childNode = new Node<>(c, node);
                (childrenIsEmpty ? node.children = new HashMap<>() : node.children).put(c, childNode);
            }
            node = childNode;
        }
        if (node.isWord) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        node.isWord = true;
        node.value = value;
        size++;
        return null;
    }

    @Override
    public V remove(String key) {
        Node<V> node = node(key);
        if (null == node || !node.isWord) return null;
        size--;

        V oldValue = node.value;
        
        if (null != node.children && !node.children.isEmpty()) { // 不是叶子节点
            node.value = null;
            node.isWord = false;
            return oldValue;
        }
        
        // 是叶子节点，向上删除
        Node<V> parent = node.parent;
        while (parent != null) {
            parent.children.remove(node.character);
            if (!parent.children.isEmpty() || parent.isWord) break;
            parent = parent.parent;
        }
        
        return oldValue;
    }

    private Node<V> node(String key) {
        keyCheck(key);
        Node<V> node = root;
        for (int i = 0, len = key.length(); i < len; i++) {
            if (node == null || node.children == null || node.children.isEmpty()) return null;
            node = node.children.get(key.charAt(i));
        }
        return node;
    }

    private void keyCheck(String key) {
        if (key == null || key.length() == 0) throw new IllegalArgumentException("Key must not be empty!");
    }

    private static class Node<V> {
        HashMap<Character, Node<V>> children;
        V value;
        boolean isWord;
        Node<V> parent;
        Character character;

        Node(Character character, Node<V> parent) {
            this.character = character;
            this.parent = parent;
        }
    }

}

总结

注意

• 解决问题时，将问题深思熟虑后进行分解，拆分为若干个子问题，然后逐个解决。

参考

小码哥李明杰老师课程: 恋上数据结构与算法 第一季.

本文完，感谢您的关注支持！