字典树

1. 什么是字典树

字典树本质上就一棵从二叉树衍生出来的多叉树

这里解释一下多叉树的数据结构类型

class TrieNode<V>{
    V val = null;//这个字段存储的是键所对应的值
    TrieNode<V>[] children = new TrieNode[256];//childeren数组存储的是指向子节点的指针
}

那么是什么含义呢?

和之前的普通多叉树的节点不同,TrieNode中children数组的索引是有意义的,代表键中的每一个字符,如果说children[c]的节点不是空,那么就说明这里存储了一个字符,而且我们可以通过指针继续遍历下去

假设这样一种场景,存在大量的相同前缀的字符串,比如说搜索引擎中的关键字:

如何使得xxx,每一个关键字都会对应一个内容,如果是用类似于哈希表这样的结构来存储的话,那么每一个关键字都要重复存储前缀,而字典树就是来解决这个问题的,它将这些前缀用树的形式组织起来,使得叶子节点上的value都能够共用这些前缀,从而达到节省空间的目的

你可以形象地这样理解,TrieNode节点本身就只存储的是val字段,并没有一个字段来存储字符,字符是通过子节点在父节点的children数组中的索引来确定的,Trie树用树枝来存储键字符串的键,用节点来存储字符串对应的值。

2. add方法编写

你可以将箭头理解为字符,将节点理解为isEnd,它的基本数据结构是基于一个字符数组+条件变量实现的

add()方法的思路是使用递归去构建你的节点,通过条件变量以及是否达到了关键字的长度,来确定是否达到了叶子节点

//在字典树中添加这个key,如果成功插入那么就返回true
//当key已经存在的时候那么就返回false
//如果插入的key是null的时候那么就返回false
//否则就是插入成功,
public boolean add(String key){
    if(key == null){
        return false;
    }
    //添加了size
    root = add(root,key,0, key.length());
    size++;
    return true;
}

//定义递归函数:从node开始开始插入key的[i....n]位置上的字母
//返回值是什么?我们从自底向上的角度来看,这个返回值在最终返回的时候就会返回一个叶子节点上去
//你也可以理解成,返回了插入了前缀[i,n-1]上所有字符的节点
//那么单层递归要做什么?它要做的就是插入当前s[i]
//如何来做这个操作的呢?它是通过`next[c] = node`,这样的方式来实现的
private TrieNode add(TrieNode node,String key,int i,int length){
    if(node == null){
        node = new TrieNode();
    }
    if(i == length){
        node.isEnd = false;
        return node;
    }
    //做一个插入当前节点的操作
    char c = key.charAt(i);
    //在node中插入了key[i]
    //递归从node.next开始插入key[i+1,n]
    node.next[c] = add(node.next[c],key,i+1,length);
    return node;
}

它插入的逻辑结构其实就是一个字符链表

这时候就会被问了,为什么要存储isEnd呢?不存储行不行呢?

答案是这样说的,因为我们在树中存储的是字符,通常来说一个连续遍历下来的字符串既有可能是一个前缀,也有可能是之前存储过的字符串,因此在这样的情况下,我们为了要检查之前是否存储过这个字符串,就可以将一个非节点的isEnd设置为true,表示我们曾经存储过这样一个字符串,来代表当前搜索路径上存在了这样一个字符串

3. 实现contains方法

/**
 * 输入一个前缀,请你返回这个前缀结束的节点
 * 情况1:返回一个空值,然后发现在树上根本就没有存在过
 * @param prefix
 * @return
 */
private TrieNode getNode(String prefix){
    //1. 健壮性检查
    if(prefix == null){
        return null;
    }
    //遍历搜索,通过指针依次向下搜索
    TrieNode cur = root;
    char[] s = prefix.toCharArray();
    for (int i = 0; i < s.length; i++) {
        if(cur == null){
            break;
        }
        cur = cur.next[s[i]];
    }
    return cur;
}

/**
 * 判断字典树上是否存在一个字符串
 * 情况2:返回一个node,判断它的isEnd是否为true,如果为true,那么就是存储的字符串
 * 情况3:返回一个node,如果isEnd为false,那么就是不是存储的字符串
 * @param key
 * @return
 */
public boolean contains(String key){
    TrieNode node = getNode(key);
    if(node == null){
        return false;
    }
    return node.isEnd;
}

4. 实现remove方法

首先明确这个方法的定义,它是给出一个key,然后你要在树上删除这个key所对应的字符串

假设你要删除team,那么你应该要删除eam这个路径,那么如何来控制算法呢?

需要有两个条件:

• 一个节点需要被删除,那么它的所有子节点都要是空的,这样才不会导致其他的节点的路径被破坏掉
• 如果在遍历的路径上,发现有一个节点的isEnd为true的时候,那么就证明有其他字符串依赖于这条路径,我们不能破坏这条路径

但是如果自己的val为false,而且自己的children的数组全都是空指针,那么就说明下面没有树枝,也就不是任何一个键的前缀,这种情况下这个节点就没有存在的意义了,应该要把自己删除掉

/**
 * 定义递归函数的定义,删除以node为根节点中,树枝上为key[i,n-1]的一条分支
 * 定义返回值:返回以node为根节点,删除树枝上为key的这条分i支后的根节点情况
 * 当node == null,代表着以node开始,向下遍历如果有且仅有一条路径为key的时候,这时候就会将node删除
 * 当node != null,代表着以node开始,向下遍历此时因为存在多条路径,有可能是存在到key的分叉,此时不会将node删除
 * @param node
 * @param key
 * @return
 */
public TrieNode remove(TrieNode node,String key,int i,int length){
    //1. 程序的健壮性检查
    if(node == null){
        return null;
    }
    //2. 开始删除操作
    //2.1 base-case:当走到这个key的最尾部的时候,将这个key的value标记为false
    if(length == i){
        node.isEnd = false;
    }
    //2.3 当前节点不为空,那么就要检查当前这个节点node是不是其他字符串的存储,如果有的话那么就直接返回
    if(node.isEnd){
        return node;
    }
    //2.2 当前节点不为空,那么就要检查当前这个node有没有子节点,如果有子节点,那么就直接原来的节点
    //这是因为如果我们直接删除这个节点,那么就会导致其他路径被破坏
    for (int j = 0; j < R; j++) {
        if(node.next[j] != null){
            return node;
        }
    }
    //否则就代表这个元素可以被删除
    return null;
}

5. 最长/最短前缀

匹配最长前缀是在干什么?

就是输入一个字符串,任何让你返回在字典树中的最长前缀是哪个

比如说字典树上存储了:

a
ab
abcd
bbcd 

输入abcdef的时候,此时应该要返回abcd

/**
 * 根据prefix查询字典树中有哪些字符串是以prefix为前缀的所有字符串
 * 基本思路,记得`getNode()`函数,它是说让你返回这个prefix中,s[n-1]为树枝指向的最后一个节点
 * 然后我们以这个node函数为起点,递归遍历这个节点下的所有子树,然后就可以得到所有的字符串了
 * @param prefix
 * @return
 */
public List<String> keyWithPrefix(String prefix){
    List<String> keys = new ArrayList<>();
    TrieNode node = this.getNode(prefix);
    if(node == null){
        return keys;
    }
    backtrack(node,new StringBuilder(prefix),keys);
    return keys;
}

//遍历以node为根节点的Trie树,然后找到所有字符串
/**
 * 回溯算法,在递归之前做出选择,在递归之前撤销选择
 * 回溯是这样的:站在node上,然后对当前的node子节点做出选择,如果node的存在树枝,那么就遍历到下一个节点
 * @param node
 * @param sb
 * @param keys
 */
private void backtrack(TrieNode node,StringBuilder sb,List<String> keys){
    if(node == null){
        return;
    }
    if(node.isEnd){
        keys.add(sb.toString());
    }
    //遍历多叉树
    for(char c = 0; c < R;c++){
        if(node.next[c] != null){
            sb.append(c);
            backtrack(node.next[c],sb,keys);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

6.leetcode208:实现Trie

public class Trie {
    public static final int R = 256;
    /*定义字典树的数据结构*/
    private class TrieNode{
        boolean isEnd;
        TrieNode[] next = new TrieNode[R];
    }
    /*定义字典树的基本变量*/
    private TrieNode root;//字典树的根节点
    private int count;//统计树上有多少个根节点

    public Trie() {
        this.count = 0;
    }
    //void insert(String word) 向前缀树中插入字符串 word
    public void insert(String word) {
        if(word == null || word.length() == 0) {
            return;
        }
        char[] s = word.toCharArray();
        root = add(root,s,0,s.length);
        this.count++;
    }

    /**
     * 在节点node上插入字符串[i,n-1]的字符
     * 返回值:以node为根节点的
     * @param node
     * @param key
     * @param index
     * @param length
     * @return
     */
    private TrieNode add(TrieNode node,char[] key,int index,int length){
        //如果要插入的对象为null,就证明树上还没有生成过这个对象
        if(node == null){
            node = new TrieNode();
        }
        //此时连接的树枝已经是已经是最后一个字符了,于是此时就直接将isEnd设置为true
        if(index == length){
            node.isEnd = true;
            //此时下面也就没有字符串
            return node;
        }
        //如果不是最后一个字符的话,那么就将取出这个字符串,继续生成
        char c = key[index];
        node.next[c] = add(node.next[c],key,index+1,length);
        return node;
    }

    /**
     * 查找字典树中是否存在这个字符串
     * @param word
     * @return
     */
    public boolean search(String word) {
        TrieNode node = this.getNode(word);
        if(node == null){
            return false;
        }
        return node.isEnd;
    }

    /**
     * 相当于从root开始查找key,找到这个key的s[n-1]连接的下一个节点
     * @param key
     * @return
     */
    private TrieNode getNode(String key){
        if(key == null || key.length() == 0){
            return null;
        }
        TrieNode cur = root;
        int length = key.length();
        for(int i = 0; i < length && cur != null;i++){
            char c = key.charAt(i);
            cur = cur.next[c];
        }
        return cur;
    }

    //不需要查找所有的元素,只需要查找到一个字符串就可以完成工作
    public boolean startsWith(String prefix) {
        TrieNode begin = getNode(prefix);
        return traverse(begin);
    }

    //遍历子节点,考察是否有满足条件的变量

    /**
     * 考察以root为起点,路径上是否有为isEnd为true的节点
     * @param root
     * @return
     */
    private boolean traverse(TrieNode root){
        if(root == null){
            return false;
        }
        if(root.isEnd){
            return true;
        }
        //否则的话就要继续查找
        for(char c = 0; c < R; c++){
            if(traverse(root.next[c])){
                return true;
            }
        }
        return false;
    }
}