TrieST

简书 賈小強
转载请注明原创出处，谢谢！

package com.lab1.test5;

import com.lab1.test1.LinkedQueue;

public class TrieST<Value> {
    private static final int R = 256;
    private Node root;
    private int n;

    private static class Node {
        Object value;
        Node[] next = new Node[R];
    }

    private Iterable<String> keysThatMatch(String pattern) {
        LinkedQueue<String> results = new LinkedQueue<>();
        collect(root, new StringBuilder(), pattern, results);
        return results;
    }

    private void collect(Node x, StringBuilder prefix, String pattern, LinkedQueue<String> results) {
        if (x == null) {
            return;
        }
        int d = prefix.length();
        if (d == pattern.length() && x.value != null) {
            results.enqueue(prefix.toString());
        }
        if (d == pattern.length()) {
            return;
        }
        char c = pattern.charAt(d);
        if (c == '.') {
            for (char ch = 0; ch < R; ch++) {
                prefix.append(ch);
                collect(x.next[ch], prefix, pattern, results);
                prefix.deleteCharAt(prefix.length() - 1);
            }
        } else {
            prefix.append(c);
            collect(x.next[c], prefix, pattern, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    private Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null) {
            return null;
        } else {
            return (Value) x.value;
        }
    }

    private Iterable<String> keys() {
        return keysWithPrefix("");
    }

    private Iterable<String> keysWithPrefix(String prefix) {
        LinkedQueue<String> results = new LinkedQueue<>();
        Node x = get(root, prefix, 0);
        collect(x, new StringBuilder(prefix), results);
        return results;
    }

    private void collect(Node x, StringBuilder prefix, LinkedQueue<String> results) {
        if (x == null) {
            return;
        }
        if (x.value != null) {
            results.enqueue(prefix.toString());
        }
        for (char c = 0; c < R; c++) {
            prefix.append(c);
            collect(x.next[c], prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    private Node get(Node x, String key, int d) {
        if (x == null) {
            return null;
        }
        if (d == key.length()) {
            return x;
        }
        char c = key.charAt(d);
        return get(x.next[c], key, d + 1);
    }

    private void delete(String key) {
        root = delete(root, key, 0);
    }

    private Node delete(Node x, String key, int d) {
        if (x == null) {
            return null;
        }
        if (d == key.length()) {
            if (x.value != null) {
                n--;
            }
            x.value = null;
        } else {
            char c = key.charAt(d);
            x.next[c] = delete(x.next[c], key, d + 1);
        }

        if (x.value != null) {
            return x;
        }
        for (char c = 0; c < R; c++) {
            if (x.next[c] != null) {
                return x;
            }
        }
        return null;
    }

    private boolean contains(String key) {
        return get(key) != null;
    }

    private boolean isEmpty() {
        return n == 0;
    }

    private int size() {
        return n;
    }

    private void put(String key, Value value) {
        root = put(root, key, value, 0);
    }

    private Node put(Node x, String key, Value value, int d) {
        if (x == null) {
            x = new Node();
        }
        if (d == key.length()) {
            if (x.value == null) {
                n++;
            }
            x.value = value;
            return x;
        }
        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, value, d + 1);
        return x;
    }

    public static void main(String[] args) {
        TrieST<Integer> st = new TrieST<>();
        String test = "she sells shell by the sea shore";
        String[] keys = test.split(" ");
        for (int i = 0; i < keys.length; i++) {
            st.put(keys[i], i);
        }
        System.out.println(st.size());
        System.out.println(st.isEmpty());
        System.out.println(st.contains("shell"));
        st.delete("shell");
        System.out.println(st.contains("shell"));
        for (String key : st.keys()) {
            System.out.println(key + " " + st.get(key));
        }
        System.out.println();
        for (String key : st.keysThatMatch("s..")) {
            System.out.println(key + " " + st.get(key));
        }
    }
}

输出

7
false
true
false
by 3
sea 5
sells 1
she 0
shore 6
the 4

sea 5
she 0

Happy learning !!