前缀树/字典树的介绍及其简单应用

介绍

前缀树是什么呢，先看一段维基百科上对它的定义：

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

要理解它首先要知道我们用这个东西的目的是什么，我举一个最直观的例子，比如要查询某个单词，很多搜索框都有搜索提示。你想查询“Hello”这个单词，当你输入“Hel”甚至输入“H”时可能提示框就已经出现了“Hello”这个单词。前缀树最常用的应用就在这里，即通过某一前缀去查到该前缀底下对应的有什么单词。有的人可能会问“那我直接把所有单词存在一个数组或者List，遍历一遍不是也能查到吗！”，确实，但你不觉得这样在查找某个单词的时候其实花了很多时间访问到了很多无用数据吗，十分的浪费时间。使用前缀树可以将查找某个单词的时间复杂度降到 O(logn)。

简单来说，首先它是一棵树，其次树中的每个结点都是当前的前缀，这样便于我们用更少的时间去查找某个元素。我再画一张图加深一下理解，为了图的简洁，假设当前单词库里就三个单词，“hi”、“me”和“min”。

好，我的废话可能有点多了，那么接下来就来看如何实现它。

实现

首先前缀树还是一课树，所以肯定少不了结点的插入、查找、删除等等。懂的了前缀树的本质，实现这些其实就是在树这个数据结构的基础上简单改变一下即可，LC208可以很好的练习前缀树的实现，这一节也根据这个来实现一个简单的前缀树。

定义数据结构

首先来定义结点，一颗树中的结点必然要有孩子结点，所以要有孩子结点的数组（或者列表），这里因为数据是英文单词，只有26个字母可以转移，所以定义一个长度为26的数组即可。

TrieNode[] childs = new TrieNode[26];

其次还需要知道当前是前缀还是已经查询到了结果，所以需要一个 boolean 来表示是否为需要查询的单词。

boolean isEnd;

初始化

创建一个根结点即可。

java复制代码/** Initialize your data structure here. */
public Trie() {
    root = new TrieNode();
}

插入

插入一个新数据时，将单词拆分成一个个字母，根据当前树中的结点判断：

若当前前缀已存在，则直接进入该结点；
若当前前缀不存在，则插入新结点，记录当前前缀。
当遍历到单词最后一个字母时，记录当前结点为一个单词。

例如在上面的例子中插入“him”这个单词如下图所示。

java复制代码/** Inserts a word into the trie. */
public void insert(String word) {
    TrieNode curr = root;

    for (char c : word.toCharArray()) {
        if (curr.childs[c - 'a'] == null) {
            curr.childs[c - 'a'] = new TrieNode();
        }
        curr = curr.childs[c - 'a'];
    }

    curr.isEnd = true;
}

查找

查找一个数据时，只需一个一个找结点匹配前缀即可，如下是查找到“min”这个单词的过程。

如下是查找“mid”这个单词失败的过程。

java复制代码/** Returns if the word is in the trie. */
public boolean search(String word) {
    TrieNode curr = root;

    for (char c : word.toCharArray()) {
        if (curr.childs[c - 'a'] == null) return false;
        curr = curr.childs[c - 'a'];
    }

    return curr.isEnd;
}

完成

到这就完成了简单的查找单词的前缀树/字典树，完整代码如下：

java复制代码class Trie {

    class TrieNode {
        boolean isEnd;
        TrieNode[] childs = new TrieNode[26];
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;

        for (char c : word.toCharArray()) {
            if (curr.childs[c - 'a'] == null) {
                curr.childs[c - 'a'] = new TrieNode();
            }
            curr = curr.childs[c - 'a'];
        }

        curr.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode curr = root;

        for (char c : word.toCharArray()) {
            if (curr.childs[c - 'a'] == null) return false;
            curr = curr.childs[c - 'a'];
        }

        return curr.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode curr = root;

        for (char c : prefix.toCharArray()) {
            if (curr.childs[c - 'a'] == null) return false;
            curr = curr.childs[c - 'a'];
        }

        return true;
    }
}

应用

前缀树的应用还是很多的，除了上述的搜索提示外，还可以用于诸如如下场景：

字符串排序：字符串按字典顺序排序，可以使用前缀树
查找两个字符串的最长公共前缀
查找某二进制数，且要按前缀顺序查找

这里，我重点介绍一下查找某二进制数这个应用

二进制数上的应用

这道LC421就淋漓尽致地展现了前缀树在二进制数上的应用。题目如下：

这道题需要我们找到两个数的最大异或结果，且只能遍历一次数组。若是单纯比较两个数大小我们会怎么比呢？比如 123 和 120 ，我们会先看百位，都是 1，那么再比较十位，都是 2，再比较个位，3 肯定比 0 大，于是我们得出结论：123 > 120。同样的，在二进制数上也是一样的比较方式，比如 111 与 110，先比较最高位都是 1，再比较第二高位，也都是 1，再比较最后一位 1 > 0，于是我们知道 111 > 110。

到这里，是不是就清楚了前缀树该怎么用了。正因为我们要从最高位比到最低位，前面的几个高位不就相当于是一个前缀吗，所以用上前缀树，我们可以遍历一遍数组，一边往树里添加数字，一遍从中寻找最大的异或值，这题就解出来了。

那么如何去寻找最大的异或值？我们都知道异或的计算是对应二进制位若相同则取0，不同则取1。我们要找最大的结果，那么肯定要尽量在高位找 1 呀。所以在我们查找时，寻找与当前数字当前位不同的即可，比如当前位是 0，那么我们就找 1；如果当前为是 1，那么我们就找 0。当然，如果找不到那就只能取一样的了，这一位总不能没有值。

下图我以查找 0100 的最大异或结果为例做一个演示：

完整代码如下：

java复制代码class Solution {

    private final int MAX_BIT = 30; // 最大位数

    private Trie root = new Trie();

    public int findMaximumXOR(int[] nums) {
        int ans = 0;

        for (int num : nums) {
            add(num);
            // 每加入一个数字找一下这个数字和当前前缀树里的数的最大异或结果
            ans = Math.max(ans, find(num));
        }

        return ans;
    }

    public void add(int num) {
        Trie cur = root;

        // 从最高位到最低位
        for (int k = MAX_BIT; k >= 0; k--) {
            int bit = (num >> k) & 1; // 计算当前位是什么

            if (bit == 0) {
                if (cur.left == null)
                    cur.left = new Trie(); // 如果不存在这个结点，就创建一个
                cur = cur.left;
            } else {
                if (cur.right == null)
                    cur.right = new Trie(); // 如果不存在这个结点，就创建一个
                cur = cur.right;
            }
        }
    }

    public int find(int num) {
        Trie cur = root;
        int res = 0;

        // 从最高位到最低位
        for (int k = MAX_BIT; k >= 0; k--) {
            int bit = (num >> k) & 1; // 计算当前位是什么

            if (bit == 0) {
                // 当前位是 0，找 1
                if (cur.right != null) {
                    res = (res << 1) + 1; // 找到 1 了，这一位可以直接置为 1
                    cur = cur.right;
                } else {
                    // 没找到
                    res = res << 1; // 没有找到 1 ，这一位就只能是 0 了
                    cur = cur.left;
                }   
            } else {
                // 当前位是 1，找 0
                if (cur.left != null) {
                    res = (res << 1) + 1; // 找到 0 了，这一位可以直接置为 1
                    cur = cur.left;
                } else {
                    // 没找到
                    res = res << 1; // 没有找到 0 ，这一位就只能是 0 了
                    cur = cur.right;
                }
            }
        }

        return res;
    }
}

class Trie {
    Trie left = null; // 记录该位为 0
    Trie right = null; // 记录该位为 1
}

进阶

看到这里，如果你觉得你懂了，跃跃欲试，就来试试LC1707吧，和上面那个如出一辙，都是寻找最大异或值，只是在此基础之上加了点限制。

总结

这篇文章也是入门了一下前缀树，其实它没有那么难理解，关键就在于如何应用它，前缀该如何定义？把到每一个结点的过程可以看作是一个状态的转移，那么在每一步又有多少种状态可以转移？像在单词的应用中，每一步有 26 个方向可以转移，即 26 个字母，而在二进制数中，每一步仅有两个方向可以转移，即 0 和 1。思考清楚这些，相信会对前缀树有更好的理解并且可以有更高级的应用。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有