【算法&数据结构体系篇class08】：前缀树

Dear 丶 2024-03-26 12:49 50阅读 0赞

### 一、前缀树（prefix tree trie） ###

1）单个字符串中，字符从前到后的加到一棵多叉树上

2）字符放在路上，节点上有专属的数据项（常见的是pass和end值）

3）所有样本都这样添加，如果没有路就新建，如有路就复用

4）沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1

可以完成前缀相关的查询

> 设计一种结构。用户可以：  
> 1）void insert(String str) 添加某个字符串，可以重复添加，每次算1个  
> 2）intsearch(String str) 查询某个字符串在结构中还有几个  
> 3) void delete(String str) 删掉某个字符串，可以重复删除，每次算1个  
> 4）intprefixNumber(String str) 查询有多少个字符串，是以str做前缀的

### 二、前缀树路的实现方式 ###

**1）固定数组实现**

**2）哈希表实现**

### 三、前缀树代码演示 ###

package class08;
    
    import java.util.HashMap;
    
    /**
     * 前缀树
     */
    public class TrieTree {
        /**
         * 固定数组实现前缀树
         */
        public static class Node1 {
            public int pass;        //记录经过该节点字符的次数
            public int end;         //记录以该节点结尾字符的次数
            public Node1[] nexts;   //节点字符往后的路径 26个字母 长度26
    
            public Node1() {
                pass = 0;
                end = 0;
                nexts = new Node1[26];
            }
        }
    
        public static class Trie1 {
            public Node1 root;
    
            public Trie1() {
                root = new Node1();
            }
    
            //添加某个字符串，可以重复添加，每次算1个
            public void insert(String str) {
                if (str == null) return;
                //不为空，转换为字符数组
                char[] chars = str.toCharArray();
                //定义一个节点对象，赋值为根节点初始值,同时给根节点的pass+1
                Node1 node = root;
                node.pass ++;
                //定义一个索引标记，来保存走a-z其中哪个路径
                int index = 0;
                for (int i = 0; i < chars.length; i++) {
                    //字符a-z范围 减去a得到0-25的范围 假设char[i]字符是b 那么index =1
                    index = chars[i] - 'a';
                    if (node.nexts[index] == null) {
                        //假设当前路径b 没有值走过，也就是第一次插入有b字符的情况，那么就需要创建一个节点，
                        node.nexts[index] = new Node1();
                    }
                    //node节点来到当前该字符节点b,继续下一个字符
                    node = node.nexts[index];
                    //给该字符节点的pass加1 表示该字符经过1次
                    node.pass++;
    
                }
                //遍历完成后，node节点就来到最后一个字符，比如str=bac 那么需要给c字符节点的end值加1 表示该节点结尾的字符有一个字符串
                node.end++;
            }
    
            //删掉某个字符串，可以重复删除，每次算1个
            public void delete(String str) {
                if (search(str) != 0) {
                    char[] chars = str.toCharArray();
                    Node1 node = root;    //定义节点从根节点开始遍历
                    node.pass --;         //删除字符串，那么根节点初始值的pass需要-1
                    int index = 0;        //定义字符串路径索引
                    for(int i = 0;i<chars.length;i++){
                        index = chars[i] - 'a';
                        //假设str= bac 只出现过依次，那么第一次来到b是--pass就为0，那么就可以直接将当前b节点赋值null 后面的也就指向会消除
                        if(--node.nexts[index].pass == 0){
                            node.nexts[index] = null;
                            return;       //给当前这个字符-1，假设减后值为0，那么就可以直接赋值null 后面的也会同时消除。因为没有指向
                        }
                        //-1后不为0 说明这节点不止有一次经过，接着到下个字符开始
                        node = node.nexts[index];
                    }
                    //整个字符遍历完 bac 假设来到c最后一个字符，发现c只有一次经过，那么在前面循环中就会将c节点赋值null了，就直接返回
                    //假设没有退出程序说明经过c不止一次，这里就需要将c节点end -1；就表示删除bac该字符串
                    node.end--;
                }
            }
    
    
            //查询某个字符串在结构中还有几个
            private int search(String str) {
                if(str == null) return 0;
                char[] chars = str.toCharArray();
                Node1 node = root;
                int index = 0;
                //遍历每个字符，有为空则表示没有，直到最后遍历完成，表示存在字符串 返回end即表示有多少个
                //这里注意，我们在insert是设计的如果是当前节点存在有那么就pass++，没有那么就会new一个节点，指向就不一样了
                //比如 bac已经插入。后面bzc 插入时，b字符节点有pass++,z节点没有 就会new节点，最后这个z的下个节点也是new的一个c节点
                //跟第一次bac的c在内存中不是同一个 所以查询bac多少个， 最后返回c节点end值 为1
                for(int i =0;i<chars.length;i++){
                    index = chars[i] - 'a';
                    if(node.nexts[index] == null) return 0;
                    node = node.nexts[index];
                }
                //最后都有字符，那么就返回在最后一个节点node的end值即标记有多少个重复的字符串
                return node.end;
            }
    
            //查询有多少个字符串，是以str做前缀的  返回用pass表示经过，不能用end，因为前缀后面也可能存在其他字符
            public int prefixNumber(String str){
                if(str == null) return 0;
                char[] chars = str.toCharArray();
                Node1 node = root;
                int index = 0;
                for(int i = 0;i < chars.length;i++){
                    index = chars[i] - 'a';
                    //如果某个路径下为空，那么直接返回0
                    if(node.nexts[index] == null) return 0;
                    node = node.nexts[index];
                }
                return node.pass;  //不为0，那么就返回最后字符节点pass值，表示str经过了多少次
            }
        }
    
        /**
         * 哈希表实现前缀树
         */
        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{
            public Node2 root;
            public Trie2(){
                root = new Node2();
            }
            public void insert(String str){
                if(str == null) return ;
                char[] chars = str.toCharArray();
                Node2 node = root;
                node.pass++;
                int index = 0;
                for(int i = 0;i<chars.length;i++){
                    index = (int)chars[i];   //这里直接将字符转换成int
                    if(!node.nexts.containsKey(index)){
                        //哈希表中没有该字符key，那么就创建一个键值对
                        node.nexts.put(index,new Node2());
                    }
                    node = node.nexts.get(index);
                    node.pass++;
                }
                node.end++;
            }
            public void delete(String str){
                if(search(str) > 0){
                    char[] chars = str.toCharArray();
                    Node2 node = root;
                    node.pass--;
                    int index = 0;
                    for(int i =0; i< chars.length ;i++){
                        index = (int)chars[i];
                        if(--node.nexts.get(index).pass == 0){
                            node.nexts.remove(index);
                            return;
                        }
                        node = node.nexts.get(index);
                    }
                    node.end--;
                }
            }
            public int search(String str){
                if(str == null) return 0;
                char[] chars = str.toCharArray();
                Node2 node = root;
                int index = 0;
                for(int i = 0;i<chars.length;i++){
                    index = (int)chars[i];
                    if(!node.nexts.containsKey(index)){
                        return 0;
                    }
                    node = node.nexts.get(index);
                }
                return node.end;
            }
            public int prefixNumber(String str){
                if(str == null) return 0;
                char[] chars =str.toCharArray();
                Node2 node = root;
                int index = 0;
                for(int i= 0;i<chars.length;i++){
                    index = (int)chars[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!");
    
        }
    }

### 四、不基于比较的排序：计数排序 &基数排序 ###

> **桶排序思想下的排序**：计数排序 &基数排序   
>   
> 1)桶排序思想下的排序都是不基于比较的排序  
>   
> 2)时间复杂度为O(N)，额外空间负载度O(M)  
>   
> 3)应用范围有限，需要样本的数据状况满足桶的划分

> 1）一般来讲，计数排序要求，样本是整数，且范围比较窄  
>   
> 2）一般来讲，基数排序要求，样本是10进制的正整数  
>   
> 一旦要求稍有升级，改写代价增加是显而易见的  
>

***代码演示：***

计数排序：

> *计数排序，\[2,4,3,8,5,9\] 取出最大值9 定义长度9+1的数组 下标就是0-9，10个桶 依次把值放到对应的索引比如*  
> *2桶放两个2，3桶放一个3....然后就依次遍历取每个桶的值*  
> *0-200的数 如果涉及负数，可以整体先加一个最小负数值，使得全部元素为正数*

package class08;
    
    import java.util.Arrays;
    
    public class CountSort {
        /**
         * 计数排序，[2,4,3,8,5,9] 取出最大值9 定义长度9+1的数组 下标就是0-9，10个桶 依次把值放到对应的索引比如
         * 2桶放两个2，3桶放一个3....然后就依次遍历取每个桶的值
         * 0-200的数 如果涉及负数，可以整体先加一个最小负数值，使得全部元素为正数
         */
        public static void countSort(int[] arr){
            if(arr == null || arr.length <2) return;
            int max =arr[0];
            //取出最大值
            for(int i = 1;i<arr.length;i++){
                max = Math.max(max,arr[i]);
            }
            //定义数组范围从0..max,把该区间的数遍历存放进去，多个相同值就累加
            int[] bucket = new int[max+1];
            for(int i = 0;i<arr.length;i++){
                bucket[arr[i]]++;
            }
            //定义数组索引，从头开始将桶的元素依次覆盖原数组
            int index = 0;
            for(int i = 0;i<bucket.length;i++){
                while(bucket[i]-- >0){
                    arr[index++] = i;
                }
            }
        }
    
        // for test
        public static void comparator(int[] arr) {
            Arrays.sort(arr);
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 150;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                countSort(arr1);
                comparator(arr2);
                if (!isEqual(arr1, arr2)) {
                    succeed = false;
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    
            int[] arr = generateRandomArray(maxSize, maxValue);
            printArray(arr);
            countSort(arr);
            printArray(arr);
    
        }
    }

基数排序：

> 基数排序 按每个数的位数来入桶，桶范围则是0-9 从个位、十位、百位依次入桶  
>  这里用了节省空间的写法，避免了使用10个桶的大量额外空间

package class08;
    
    import java.time.LocalDate;
    import java.util.Arrays;
    
    public class RadixSort {
        /**
         * 基数排序 按每个数的位数来入桶，桶范围则是0-9 从个位、十位、百位依次入桶
         * 这里用了节省空间的写法，避免了使用10个桶的大量额外空间
         *
         */
        public static void radixSort(int[] arr){
            if(arr == null || arr.length < 2){
                return;
            }
            //1。获取数组最大值有多少位
            int digit = maxbits(arr);
            //2.定义一个辅助存放每次按位排序后的结果
            int[] help = new int[arr.length];
            //3.开始按位遍历
            for(int i = 1;i<=digit;i++){
                //4.建议0-9的下标索引数组桶，将每次个位十位百位..的值的元素对应入桶
                int[] count = new int[10];
                for(int j = 0;j<arr.length;j++){
                    //5.i=1 遍历每个元素个位的值，对应该值给count桶累加1，比如123，i-1
                    //个位值为3，给count[3]++
                    count[getBit(arr[j],i)]++;
                }
                //6.接着将count存放的内容，转换成前缀和。 外循环i=1:表示count[0]个位小于等于0的个数
                //count[1] 个位小于等于1的个数...
                for(int j = 1;j<count.length;j++){
                    count[j] = count[j] + count[j-1];
                }
                //7.从右往左，将元素赋值到辅助数组中,假设最后一个元素 123, 当前外循环i =1,
                //按个位排序，123的个位是3，那么就找count[3]的值 假设为5，表示个位小于等于3
                //的元素有5个，应该排序在help数组的0-4下标位置，因为我们是从右往左找，所以当前123
                //这个靠右的元素就放到help最右边界下标arr[4]中，依次类推，然后到i=2十位再对比排序
                for(int j = arr.length-1;j>=0;j--){
                    //getBit(arr[j],i)获取123的个位3  count[3] - 1 count[3]有5个，123放在最右下标4 ，
                    //所以-1，该位置就赋值arr[j] 123
                    int num = getBit(arr[j],i);
                    help[count[num]-1]=arr[j];
                    //8.关键一步，把当前桶的值移入辅助数组后，需要对应桶数量-1
                    count[num]--;
                }
                //8.最后help赋值完就开始覆盖给原数组，i=1 覆盖完个位的排序，i=2再覆盖十位的排序...
                for(int j = 0;j<arr.length;j++){
                    arr[j] = help[j];
                }
            }
        }
    
        //返回i元素第j位的值， 比如123  1， 返回3 即123的个位值等于3
        private static int getBit(int i, int j) {
            return ( i / ((int)Math.pow(10,j-1))) %10;
        }
    
        //获取数组最大值的位数 比如100  返回3位 1000 返回4位
        private static int maxbits(int[] arr) {
            int max = arr[0];
            for(int i = 1;i<arr.length;i++){
                max = Math.max(max,arr[i]);
            }
            int ans = 1;
            while((max / 10) > 0){
                ans++;
                max /=10;
            }
            return ans;
        }
    
        // for test
        public static void comparator(int[] arr) {
            Arrays.sort(arr);
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            System.out.println(LocalDate.now().getMonthValue());
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100000;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                radixSort(arr1);
                comparator(arr2);
                if (!isEqual(arr1, arr2)) {
                    succeed = false;
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    
            int[] arr = generateRandomArray(maxSize, maxValue);
            printArray(arr);
            radixSort(arr);
            printArray(arr);
    
        }
    
    }

### 五、排序算法的稳定性 ###

> **稳定性是指同样大小的样本再排序之后不会改变相对次序**  
>   
> 对基础类型来说，稳定性毫无意义  
>   
> 对非基础类型来说，稳定性有重要意义  
>   
> 有些排序算法可以实现成稳定的，而有些排序算法无论如何都实现不成稳定的

### 六、排序算法总结 ###

> **时间复杂度 额外空间复杂度 稳定性**  
> 选择排序 O(N^2) O(1) 无  
> 冒泡排序 O(N^2) O(1) 有  
> 插入排序 O(N^2) O(1) 有  
> 归并排序 O(N\*logN) O(N) 有  
> 随机快排 O(N\*logN) O(logN) 无  
> 堆排序 O(N\*logN) O(1) 无  
> ================================================计数排序 O(N) O(M) 有  
> 基数排序 O(N) O(N) 有  
>

> 1）不基于比较的排序，对样本数据有严格要求，不易改写  
> 2）基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用  
> 3）基于比较的排序，时间复杂度的极限是O(N\*logN)  
> 4）时间复杂度O(N\*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。  
> 5）为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

### 七、常见的坑 ###

> 1）归并排序的额外空间复杂度可以变成O(1)，“归并排序内部缓存法”，但是将变得不再稳定。  
>   
> 2）“原地归并排序"是垃圾贴，会让时间复杂度变成O(N^2)  
>   
> 3）快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多。  
>   
> 4）在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。  
>   
> 时间复杂度做到O(N)，额外空间复杂度做到O(1)  
>

### 八、工程上对排序的改进 ###

> 1)稳定性的考虑（稳定性就是相同对象，次序不发生改变）  
> 比如Java中的Arrays.sort()系统自带排序功能,当排序元素是基本数据类型比如int,float等这一类型都是比较数值，都是一致的，不需要稳定性的说法，那么底层源码设计时会用改进后的快排算法来进行排序,时间复杂度小,不稳定。而假设时非基础数据类型，如自定义类,系统就会考虑是否业务需要类对象有序，要具有稳定性，那么就采用稳定性的归并排序算法  
>   
> 2)充分利用O(N\*logN)和O(N^2)排序各自的优势  
> 比如快排改进：l==r时直接就 return; 改成 (l + 60) >r\{执行插入排序\}那么表示数据量60以内的用插入排序，大于60用快排；N小，插入排序的时间复杂度也有可能比快排小，因为N小了，而且插入排序的常数项小，快排常数项大  
> 60这个值是经过实验证明的一个量级