前缀树Trie的实现

前缀树

Trie树，也叫做字典树，是一种有序树，用于保存一种映射关系，其中映射的键通常为字符串，且键并不直接保存在节点中，而是由节点在树中的位置决定。一个节点所有的子孙都具有相同的前缀，也就是该节点所对应的字符串，而跟节点对应空字符串。一般情况下，不是所有的节点都有对应的值，而是只有叶子节点和部分内部节点所对应的键才有相关的值。

应用： Trie树常用于搜索提示。比如当输入一个网址，可以自动搜索出其他可能的选择，当没有完全匹配的搜索结果时，可以返回前缀最相似的可能值。

结构分析

Trie的节点结构：

class TrieNode {
  //用来标示该节点是否为一个串的结束节点
  private boolean isEnd;
  //字母映射表（26个位置对应26个字母）
  private TrieNode[] next;
}

字符串（word）插入

首先从跟节点的子节点开始与word第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的节点，知道插入完word的最后一个字符，同时将结束标记为设置为true

void insert(String word) {
  //用新的引用进行遍历
  TrieNode node = root;
  for (char c : word.toCharArray()) {
    if (node.next[c - 'a'] == null) {
      node.next[c - 'a'] = new TrieNode();
    }
    node = node.next[c - 'a'];
  }
  node.isEnd = true;
}

字符串（word）查找

从根节点的子节点开始，一直向下匹配，若出现节点值为空的情况说明没找到返回false，如果匹配到了最后一个字符，则判断该节点是否为一个字符串的结束节点即可。

public boolean search(String word) {
  TrieNode node = root;
  for (char c : word.toCharArray()) {
    if (node.next[c - 'a'] == null) {
      return false;
    }
    node = node.next[c - 'a'];
  }
  return node.isEnd;
}

前缀匹配

与搜索完全一致，区别在于无需判断最后一个字符对应的节点是否为某个串的结束节点。

性质

Trie树的形状与单词的插入或删除顺序无关，即给定一组单词，Trie树的形状时唯一的
查找或插入一个长度为L的单词，访问next数组的最大次数为L+1次，和Trie树中包含着多少个单词无关
Trie树中每个节点都保留着一个字母表，有空间浪费。若Trie树的高度为n，字母表的大小为m（一般常见英文字母表为26，但其他语言不一定），那么最坏情况下，即Trie树中没有相同前缀的单词，空间复杂度为O(m^n)

实现代码

/**
 * 实现前缀树（Trie）
 * @author wei
 * @since 2021/5/23
 */
public class Trie {

    private final TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new TrieNode();
            }
            node = node.next[c - 'a'];
        }
        node.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                return false;
            }
            node = node.next[c - 'a'];
        }
        return node.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                return false;
            }
            node = node.next[c - 'a'];
        }
        return true;
    }


    private static class TrieNode {
        private Boolean isEnd;
        private TrieNode[] next;

        public TrieNode() {
            this.isEnd = false;
            this.next = new TrieNode[26];
        }

        public Boolean getEnd() {
            return isEnd;
        }

        public void setEnd(Boolean end) {
            isEnd = end;
        }

        public TrieNode[] getNext() {
            return next;
        }

        public void setNext(TrieNode[] next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Trie t = new Trie();
        t.insert("word");
    }
}

发布于 2021-05-23