Skip to main content
 首页 » 编程设计

Java字典树(Trie)数据结构

2022年07月19日170mayingbao

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. 插入元素

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

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

该操作的时间复杂度为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. 查找元素

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

  1. 获得根节点子节点
  2. 迭代字符串的每个字符
  3. 检查当前字符是否为字典子树的一部分,如果一直查询不到,停止返回false。
  4. 重复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. 删除元素

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

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

时间复杂度为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
阅读延展