Java字典树(Trie)数据结构_编程设计

Java字典树(Trie)数据结构

数据结构计算机编程中的关键内容，了解什么时候使用以及为什么使用是非常重要的。本文介绍字典树(Trie,发音try)数据结构，理解其实现并分析其复杂度。

1. 字典树(Trie)

字典树不是很知名，一般课程中提及不多，但不代表其不重要。有时也称为基数树和前缀树（因为能根据前缀进行搜索），它是基于树的数据结构，节点存储的字符（通常为字符串中的字符），通过向下遍历树的分支路径可以获得单词或字符串。

节点在树中的位置定义了与该节点相关联的键，这与二叉搜索树不同，二叉搜索树中节点存储的键只对应于该节点。节点所有后代具有相同的前缀，根节点关联空字符串。

首先看TrieNode节点类的实现：

import java.util.HashMap; 
import java.util.Map; 
 
class TrieNode { 
    private final Map<Character, TrieNode> children = new HashMap<>(); 
    private boolean endOfWord; 
 
    Map<Character, TrieNode> getChildren() { 
        return children; 
    } 
 
    boolean isEndOfWord() { 
        return endOfWord; 
    } 
 
    void setEndOfWord(boolean endOfWord) { 
        this.endOfWord = endOfWord; 
    } 
}

有可能字典树是二叉搜索树，但一般情况下两种是不同的。两种都为树，但二叉搜索数总是有两个节点，而字典树可能有多个节点（如果存储英文单词，最多有26个节点）。
字典树(除了根节点)存储一个字符或数字。通过从根节点开始向下遍历至特定节点n，能获得字符串或数字的相同前缀，即分支所共享的前缀。

如果从一个叶子节点向上遍历至根节点，则可以获得一个字符串或数字序列。下面请看Trie类的实现：

public class Trie { 
    private TrieNode root; 
 
    Trie() { 
        root = new TrieNode(); 
    } 
}

2. 字典树操作

下面讨论字典树的基本操作。

2.1. 插入元素

在描述插入新节点之前，先理解其算法：

设置当前节点为根节点
取单词的第一个字母作为当前字母
如果当前节点已经存在当前字母的引用(查找当前节点的所有子元素)，那么设置当前节点为该引用的节点。否则创建一个新的节点，设置该字母为当前字母并初始化当前节点为新的节点。
重复第三步直到字符串遍历完成。

该操作的时间复杂度为O(n),n表示字符串长度。实现如下：

public void insert(String word) { 
    TrieNode current = root; 
  
    for (int i = 0; i < word.length(); i++) { 
        current = current.getChildren() 
          .computeIfAbsent(word.charAt(i), c -> new TrieNode()); 
    } 
    current.setEndOfWord(true); 
}

现在我们看看如何使用该方法插入元素：

private Trie createExampleTrie() { 
    Trie trie = new Trie(); 
  
    trie.insert("Programming"); 
    trie.insert("is"); 
    trie.insert("a"); 
    trie.insert("way"); 
    trie.insert("of"); 
    trie.insert("life"); 
  
    return trie; 
}

通过下面测试代码可以测试字典树是否为空：

@Test 
public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { 
    Trie trie = createTrie(); 
  
    assertFalse(trie.isEmpty()); 
}

2.2. 查找元素

现在考虑实现查找方法实现：

获得根节点子节点
迭代字符串的每个字符
检查当前字符是否为字典子树的一部分，如果一直查询不到，停止返回false。
重复2、3两步，直到遍历完字符串所有字符。如果到达最后字符串返回true。

算法复杂度为O(n)，n为字符串长度。Java代码实现：

    boolean containsNode(String word) { 
        TrieNode current = root; 
 
        for (int i = 0; i < word.length(); i++) { 
            char ch = word.charAt(i); 
            TrieNode node = current.getChildren().get(ch); 
            if (node == null) { 
                return false; 
            } 
            current = node; 
        } 
        return current.isEndOfWord(); 
    }

测试代码：

@Test 
public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { 
    Trie trie = createExampleTrie(); 
  
    assertFalse(trie.containsNode("3")); 
    assertFalse(trie.containsNode("vida")); 
    assertTrue(trie.containsNode("life")); 
}

2.3. 删除元素

除了插入、查找元素，显然还需要能够删除元素。
对于删除过程，需要下面两个步骤：

检查元素是否为字典树的一部分
如果是则从字典树中删除

时间复杂度为O(n)，n表示字符串长度。java实现：

public void delete(String word) { 
    delete(root, word, 0); 
} 
  
private boolean delete(TrieNode current, String word, int index) { 
    if (index == word.length()) { 
        if (!current.isEndOfWord()) { 
            return false; 
        } 
        current.setEndOfWord(false); 
        return current.getChildren().isEmpty(); 
    } 
    char ch = word.charAt(index); 
    TrieNode node = current.getChildren().get(ch); 
    if (node == null) { 
        return false; 
    } 
    boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); 
  
    if (shouldDeleteCurrentNode) { 
        current.getChildren().remove(ch); 
        return current.getChildren().isEmpty(); 
    } 
    return false; 
}

测试代码：

@Test 
void whenDeletingElements_ThenTreeDoesNotContainThoseElements() { 
    Trie trie = createTrie(); 
  
    assertTrue(trie.containsNode("Programming")); 
   
    trie.delete("Programming"); 
    assertFalse(trie.containsNode("Programming")); 
}

3. 总结

本文介绍字典树数据结构以及其常用的操作和实现。

本文参考链接：https://blog.csdn.net/neweastsun/article/details/103878566