前缀树

• 前缀树定义

  • 前缀树（Trie树），又称字典树、单词查找树或键树，是一种专门设计用于高效存储和检索字符串集合中词项的树形数据结构。其核心特性在于能够快速实现字符串的前缀匹配，极大减少了无谓的字符比较，从而提高了查询效率。

• 前缀树的特性

  • 前缀编码
    • 每个节点代表一个字符串前缀，从根节点到任一节点的路径上的字符序列构成该节点对应的前缀。
    • 整棵树编码了所有存储在其中的字符串及其所有前缀。
  • 唯一路径
    • 树中不存在两条路径表示相同的前缀，保证了每个前缀在树中仅有一条对应路径，避免了重复存储。
  • 字符导向
    • 每个节点的子节点按字符集（通常是字母表）中的字符进行组织，边标签表示字符。
    • 从一个节点到其子节点的转移代表了字符串中字符的添加或延续。
  • 高效查询
    • 支持快速的字符串前缀查询：只需从根节点开始，沿着待查询前缀的字符顺序逐层向下遍历，即可判断该前缀是否存在。
    • 如果查询路径在树中完整存在，可以立即得知待查询前缀存在于词典中；否则，路径在某处中断，表明不存在。
  • 自动去重
    • 由于每个前缀对应树中唯一的路径，所以在插入过程中，重复的字符串（及其所有前缀）会被自动识别并忽略，无需额外的去重操作。

• 构建前缀树

  1. 初始化根节点:创建一个空节点作为前缀树的根节点，通常标记为空字符或特殊值（如null、'_'等），表示没有任何字符。
  2. 遍历输入字符串集合:对于输入的每一个字符串（词项），按照以下步骤将其插入到前缀树中。
  3. 插入单个字符串:从根节点开始,逐个字符处理当前字符
     1. 检查当前节点:查看当前节点是否有与当前字符相匹配的子节点。如果有，则沿着该子节点继续处理下一个字符；如果没有，则创建一个新的子节点，将该子节点与当前字符关联，并将其父节点设置为当前节点。
     2. 递归插入:重复步骤a，处理剩余字符，直至字符串结束。
     3. 标记词结束标记:当处理完字符串的最后一个字符时，将该节点标记为词项结束节点（如设置一个布尔标志isEndOfWord为true，或在节点中记录一个计数器end等）以表示当前路径代表一个完整的词项。
  4. 处理完所有字符串:当所有输入字符串都已按照上述过程插入到前缀树中，构建过程结束，得到的树结构即为包含所有输入字符串及其前缀的前缀树。

• 代码实现

  public class Trie {static class TrieNode{char ch;//字符boolean isEndOfWord;//是否为完整词项//子节点映射Map<Character, TrieNode> children;public TrieNode(char ch) {this.ch = ch;this.isEndOfWord=false;this.children=new HashMap<>();}}private final TrieNode root;public Trie() {this.root = new TrieNode('\0');//用'\0'代表根节点}//1.插入节点public void insert(String word){//从根节点开始插入TrieNode current=root;//遍历待查询字符串每个字符for (char ch:word.toCharArray()){/*** 这句代码 current.children.computeIfAbsent(ch, TrieNode::new) 的作用是*1.在当前节点 current 的子节点映射 children 中查找键为 ch 的条目。* 2.如果找到了，返回与 ch 关联的子节点。* 3.如果没找到，使用 TrieNode 构造函数（通过 TrieNode::new 方法引用）创建一个新的 TrieNode 实例，* 其中字符属性 ch 设置为传递给 computeIfAbsent 的 ch 参数，并将这个新创建的节点作为新值添加到映射中（键为 ch），* 然后返回这个新创建的节点。*/current=current.children.computeIfAbsent(ch,TrieNode::new);}//标记当前节点为词项的结束节点current.isEndOfWord=true;}//2.查询字符串是否存在于前缀树中public boolean search(String word){//从根节点开始TrieNode current = root;//遍历每个字符for (char ch:word.toCharArray()){//获取与当前节点对应的子节点,若不存在返回nullTrieNode node = current.children.get(ch);if (node==null){return false;}current=node;}return current.isEndOfWord;}//3.删除字符串public boolean delete(TrieNode currentNode,String word,int index){//1.若处理完所有字符串if (index==word.length()){//若不是则说明字符串不在树中,返回falseif (!currentNode.isEndOfWord){return false;}//将当前节点的词项结束标点设置为falsecurrentNode.isEndOfWord=false;//检查当前节点是否还有其他节点return currentNode.children.isEmpty();}//2.若还有字符串没有处理完//获取待删除字符串的当前节点char ch = word.charAt(index);//2.1获取当前节点的子节点,若该节点不存在,返回nullTrieNode node = currentNode.children.get(ch);if (node==null){return false;}//2.2若找到子节点,递归删除boolean shouldDeleteCurrentNode = delete(node, word, index + 1);//2.3如果递归删除子节点后返回true,说明子节点没有了其他节点,该子节点已无用可以删除if (shouldDeleteCurrentNode){currentNode.children.remove(ch);//若当前节点无其他子节点,就删除该节点return currentNode.children.isEmpty();}//2.4若此节点无需删除,返回falsereturn false;}
  }
  

• 前缀树的时间复杂度分析

  • 时间复杂度
    • 插入:构建前缀树时，插入一个字符串的时间复杂度通常为 O(L), 其中 L 是字符串的长度。这是因为插入过程中需要遍历整个字符串，为每个字符创建或查找相应的节点。
    • 查询:查询一个字符串（或其前缀）是否存在于前缀树中的时间复杂度为 O(L)，因为同样需要遍历整个字符串，沿着树结构逐个比较字符。
    • 删除:删除一个字符串的时间复杂度理论上也为 O(L)，因为需要找到该字符串在树中的完整路径。
  • 空间复杂度

• 前缀树的应用

  • 自动补全:在搜索引擎、文本编辑器、编程IDE或手机输入法中，当用户输入一部分字符时，系统能够快速列出所有可能的、以当前输入为前缀的完整词汇供用户选择。
  • 词频统计与排序:前缀树可用于统计大量文本数据中各单词出现的频率，并支持按照字母顺序输出。每个节点的计数可以表示以该节点为终点的词频，同时，由于前缀树的天然排序特性，可以按字典序遍历节点及其子节点来获取有序的单词列表。
  • 拼写检查与纠正:在文字处理软件或在线文本编辑平台中，前缀树可以帮助快速识别用户输入的单词是否存在于词库中，从而提示可能的拼写错误。
  • ip路由表查询:在计算机网络中，路由器使用前缀树（通常称为PATRICIA树或Ternary Search Tree）来存储和查找IP地址前缀，以确定数据包的下一跳转发地址。
  • 数据压缩:在某些数据压缩算法中，如LZ78，前缀树用于存储已出现过的字符串及其编码，新出现的字符串可以以其最长前缀作为索引来查找编码，