前缀树的增删改查

/* *

可以完成前缀相关的查询要完成的功能: 前缀树节点的增删查* 一切都以增加 方法为基础 一旦这个会了  其他都是衍生* Node1数据结构 那个数组代表的意义要理解 不然会无法继续*
增加*  支撑结构, pass不为null说明有这个路径, ascii码转数字*  逻辑: 假定有个头节点root, 来一个非空的  节点来到root位置 pass++   //简单处理头节点*  遍历字符串数组, 和'a'相减转成path 如果为null 则新增一个节点  //统一处理共同的逻辑*  节点来到下一个节点, pass++*  跳出循环后 end++  //简单处理末尾节点*查找*  逻辑:*  遍历字符串数组, 和'a'相减转成path 如果为null 则返回0*  跳出循环后 给出末尾节点end*共同前缀*  逻辑:*  遍历字符串数组, 和'a'相减转成path 如果为null 则返回0*  跳出循环后 给出末尾节点pass**删除* 先用search确定是否有该路径* 和增加的逻辑反着来就好* 沿路pass--, 一旦遇到下一个节点pass--后为零 得出后面的没必要走了, 节点=null  return* node.e--  //因为毕竟是一条完整的路径 必定会有这么一个节点来结尾的 除非上面发现pass只剩1了就提前结束* */

public class Code02_TrieTree_done {    //支撑class,  pass, end 和nexts数组 用来指向后面的节点
    public static class Node1 {        int pass;        int end;        Node1[] nexts;
        public Node1() {            pass = 0;            end = 0;            nexts = new Node1[26];  // 和'a'相减得到ascii 如果nexts[path]非null 则代表存在这条路径        }    }
    public static class Trie1 {        private Node1 root;
        public Trie1() {            root = new Node1();        }
        public void insert(String word) {            //判空            if (word == null || "" == word) return;            //简单处理root节点            Node1 temp = root;            temp.pass++;            int path = 0;            //循环处理 word=> 字符串 共同逻辑:  经过的pass++, 跳到下一个节点 for 下一个字符            char[] chars = word.toCharArray();            for (int i = 0; i < chars.length; i++) {                path = chars[i] - 'a';                if (temp.nexts[path] == null) {                    temp.nexts[path] = new Node1();                }                temp.nexts[path].pass++;                temp = temp.nexts[path];            }            //简单处理尾部节点end++            temp.end++;        }
        // word这个单词之前加入过几次        public int search(String word) {            //判空            if (word == null || "" == word) return 0;            //简单处理root节点            Node1 temp = root;            int path = 0;            //循环处理 word=> 字符串 共同逻辑:   跳到下一个节点 for 下一个字符            char[] chars = word.toCharArray();            for (int i = 0; i < chars.length; i++) {                path = chars[i] - 'a';                if (temp.nexts[path] == null) {                    return 0;                }                temp = temp.nexts[path];            }            return temp.end;        }

        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的        public int prefixNumber(String pre) {            if (pre == null || "" == pre) return 0;            //简单处理root节点            Node1 temp = root;            int path = 0;            //循环处理 word=> 字符串 共同逻辑:  跳到下一个节点 for 下一个字符            char[] chars = pre.toCharArray();            for (int i = 0; i < chars.length; i++) {                path = chars[i] - 'a';                if (temp.nexts[path] == null) {                    return 0;                }                temp = temp.nexts[path];            }            return temp.pass;        }
        public void delete(String word) {            if(search(word)==0) return;            //判空            if (word == null || "" == word) return;            //简单处理root节点            Node1 temp = root;            temp.pass--;            int path = 0;            char[] chars = word.toCharArray();            for (int i = 0; i < chars.length; i++) {                path = chars[i] - 'a';                if (temp.nexts[path].pass == 1) {  //一旦碰到下一个节点的pass只剩1了那么说明就这一条支路 完全删除即可                    temp.nexts[path] = null;                    return;                }                temp.nexts[path].pass--;                temp = temp.nexts[path];            }            temp.end--;        }
    }
    public static class Node2 {        public int pass;        public int end;        public HashMap<Integer, Node2> nexts;
        public Node2() {            pass = 0;            end = 0;            nexts = new HashMap<>();        }    }
    public static class Trie2 {        private Node2 root;
        public Trie2() {            root = new Node2();        }
        public void insert(String word) {            if (word == null) {                return;            }            char[] chs = word.toCharArray();            Node2 node = root;            node.pass++;            int index = 0;            for (int i = 0; i < chs.length; i++) {                index = (int) chs[i];                if (!node.nexts.containsKey(index)) {                    node.nexts.put(index, new Node2());                }                node = node.nexts.get(index);                node.pass++;            }            node.end++;        }
        public void delete(String word) {            if (search(word) != 0) {                char[] chs = word.toCharArray();                Node2 node = root;                node.pass--;                int index = 0;                for (int i = 0; i < chs.length; i++) {                    index = (int) chs[i];                    if (--node.nexts.get(index).pass == 0) {                        node.nexts.remove(index);                        return;                    }                    node = node.nexts.get(index);                }                node.end--;            }        }
        // word这个单词之前加入过几次        public int search(String word) {            if (word == null) {                return 0;            }            char[] chs = word.toCharArray();            Node2 node = root;            int index = 0;            for (int i = 0; i < chs.length; i++) {                index = (int) chs[i];                if (!node.nexts.containsKey(index)) {                    return 0;                }                node = node.nexts.get(index);            }            return node.end;        }
        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的        public int prefixNumber(String pre) {            if (pre == null) {                return 0;            }            char[] chs = pre.toCharArray();            Node2 node = root;            int index = 0;            for (int i = 0; i < chs.length; i++) {                index = (int) chs[i];                if (!node.nexts.containsKey(index)) {                    return 0;                }                node = node.nexts.get(index);            }            return node.pass;        }    }
    public static class Right {
        private HashMap<String, Integer> box;
        public Right() {            box = new HashMap<>();        }
        public void insert(String word) {            if (!box.containsKey(word)) {                box.put(word, 1);            } else {                box.put(word, box.get(word) + 1);            }        }
        public void delete(String word) {            if (box.containsKey(word)) {                if (box.get(word) == 1) {                    box.remove(word);                } else {                    box.put(word, box.get(word) - 1);                }            }        }
        public int search(String word) {            if (!box.containsKey(word)) {                return 0;            } else {                return box.get(word);            }        }
        public int prefixNumber(String pre) {            int count = 0;            for (String cur : box.keySet()) {                if (cur.startsWith(pre)) {                    count += box.get(cur);                }            }            return count;        }    }
    // for test    public static String generateRandomString(int strLen) {        char[] ans = new char[(int) (Math.random() * strLen) + 1];        for (int i = 0; i < ans.length; i++) {            int value = (int) (Math.random() * 6);            ans[i] = (char) (97 + value);        }        return String.valueOf(ans);    }
    // for test    public static String[] generateRandomStringArray(int arrLen, int strLen) {        String[] ans = new String[(int) (Math.random() * arrLen) + 1];        for (int i = 0; i < ans.length; i++) {            ans[i] = generateRandomString(strLen);        }        return ans;    }
    public static void main(String[] args) {        int arrLen = 100;        int strLen = 20;        int testTimes = 100000;        for (int i = 0; i < testTimes; i++) {            String[] arr = generateRandomStringArray(arrLen, strLen);            Trie1 trie1 = new Trie1();            Trie2 trie2 = new Trie2();            Right right = new Right();            for (int j = 0; j < arr.length; j++) {                double decide = Math.random();                if (decide < 0.25) {                    trie1.insert(arr[j]);                    trie2.insert(arr[j]);                    right.insert(arr[j]);                } else if (decide < 0.5) {                    trie1.delete(arr[j]);                    trie2.delete(arr[j]);                    right.delete(arr[j]);                } else if (decide < 0.75) {                    int ans1 = trie1.search(arr[j]);                    int ans2 = trie2.search(arr[j]);                    int ans3 = right.search(arr[j]);                    if (ans1 != ans2 || ans2 != ans3) {                        System.out.println("Oops!");                    }                } else {                    int ans1 = trie1.prefixNumber(arr[j]);                    int ans2 = trie2.prefixNumber(arr[j]);                    int ans3 = right.prefixNumber(arr[j]);                    if (ans1 != ans2 || ans2 != ans3) {                        System.out.println("Oops!");                    }                }            }        }        System.out.println("finish!");
    }
}