迹忆客 专注技术分享

本文介绍了 Java 中的 Trie 数据结构。

Java 中的 Trie 数据结构

Trie 词是从单词 Retrieval 中提取出来的，它是一种用于存储字符串集合的排序数据结构。 Trie可以定义为指针数量等于每个节点中字符数量的数据结构。

借助单词前缀，Trie 数据结构可用于从字典中搜索单词。 在这种情况下，如果字典中的所有单词都由 26 个英文字母组成，则每个 Trie 节点将有 26 个点。

Trie 数据结构也称为前缀树或数字树，其中节点的位置将决定该节点将连接的键。 我们尝试通过下图来了解 Trie 的工作原理：

上图包含了单词 deal、delft 和 delete 的树结构。

Trie 数据结构的属性

以下是字符串 Trie 集的主要属性：

1. 根节点始终为空节点。
2. 每个子节点都将按字母顺序排序。
3. 由于英文字母的原因，每个节点不能有超过 26 个子节点。
4. 每个节点可以存储字母表中的一个字母。

Trie数据结构的应用

让我们看看Trie数据结构的一些主要应用：

1. 当需要假设所有字母都是小写时，可以使用 Trie。
2. 当我们只能使用 a-z 的字母，没有连字符，没有标点符号等时。
3. 当单词的长度有限时。 例如，如果我们正在处理 2x2 的板，则字长不能超过 4，因此可以丢弃这些字。
4. 字典中的许多单词具有相同的词干，例如草坪和割草机。 Trie 可以用于这些词形变化的单词。

Trie数据结构的基本操作

Trie 具有三个基本操作：

插入操作

第一个操作是向 Trie 中插入一个节点。 为此，我们需要了解以下几点：

1. 输入单词的每个字母都将作为个体插入到 Trie 节点中。
2. 字符长度将决定 Trie 的长度。
3. 键字符数组将充当子项的索引。
4. 如果当前节点有对当前字母的引用，则设置引用该节点的当前节点。 否则，应创建一个新节点。

搜索操作

Trie 的第二个基本操作是搜索节点。 这个操作也和插入类似。

我们只需使用相同的方法搜索节点即可。

删除操作

第三个操作是删除节点。 这也是一个简单的操作。

在开始删除之前我们必须考虑两点：

1. 如果搜索时没有找到节点键，则删除操作将停止并退出。
2. 如果在搜索 Trie 时找到节点键，则删除操作将删除该键。

Trie数据结构的Java实现

我们来尝试实现Trie数据结构，它只支持小写a-z英文字符。 参见示例：

package jiyik;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


class Trie_Node {
    // 26 characters for a – z
    private static final int CHARACTER_SIZE = 26;

    private boolean Is_Leaf;
    private List<Trie_Node> Trie_Children = null;

    // Constructor
    Trie_Node(){
        Is_Leaf = false;
        Trie_Children= new ArrayList<>(Collections.nCopies(CHARACTER_SIZE, null));
    }

    // function for insertion
    public void Insertion(String Node_Key) {
        System.out.println("Inserting the key \"" + Node_Key + "\"");

        // root node
        Trie_Node root_node = this;

        // repeat for every character of the key
        for (char character: Node_Key.toCharArray()) {
            // create a new Trie node if the path does not exist
            if (root_node.Trie_Children.get(character - 'a') == null) {
                root_node.Trie_Children.set(character - 'a', new Trie_Node());
            }

            // going to the next node
            root_node = root_node.Trie_Children.get(character - 'a');
        }

        //current node as a leaf
        root_node.Is_Leaf = true;
    }

    // Method for search
    public boolean Searching(String Node_Key) {
        System.out.print("Searching the key \"" + Node_Key + "\" : ");

        Trie_Node Current_Node = this;

        // repeat for the character of the key
        for (char character: Node_Key.toCharArray()) {
            // going to the next node
            Current_Node = Current_Node.Trie_Children.get(character - 'a');

            // reach out to the end of a path in the Trie if the string is invalid
            if (Current_Node == null) {
                return false;
            }
        }
        return Current_Node.Is_Leaf;
    }
}

public class Example {
    public static void main (String[] args) {
        // construct a new Trie node
        Trie_Node New_Trie = new Trie_Node();

        New_Trie.Insertion("delft");
        New_Trie.Insertion("delf");
        New_Trie.Insertion("del");

        System.out.println(New_Trie.Searching("del"));            // true
        System.out.println(New_Trie.Searching("delf"));           // true
        System.out.println(New_Trie.Searching("delft"));          // true
        System.out.println(New_Trie.Searching("jiyik"));   // false

        New_Trie.Insertion("jiyik");

        System.out.println(New_Trie.Searching("del"));            // true
        System.out.println(New_Trie.Searching("delf"));           // true
        System.out.println(New_Trie.Searching("delft"));          // true
        System.out.println(New_Trie.Searching("jiyik"));   // true

    }
}

上面的代码实现了Trie数据结构的插入和查找操作。 查看输出：

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "jiyik" : false
Inserting the key "jiyik"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "jiyik" : true

现在，Trie 数据结构的空间复杂度为 O(N × M × C)，其中：

• N - 字符串数量
• M - 字符串的最大长度。
• C - 字母表的大小

因此，在具有上述空间复杂度的Java中，可能会出现存储问题。

我们还可以利用Java中的HashMap来实现Trie来解决存储问题。 让我们尝试使用 HashMap 来实现 Trie：

package jiyik;

import java.util.HashMap;
import java.util.Map;

class Trie_Node{
    private boolean Is_Leaf;
    private Map<Character, Trie_Node> Trie_Children;

    // Constructor
    Trie_Node()
    {
        Is_Leaf = false;
        Trie_Children = new HashMap<>();
    }

    // Insertion
    public void Insertion(String Node_Key)
    {
        System.out.println("Inserting the key \"" + Node_Key + "\"");

        // root node
        Trie_Node root_node = this;

        for (char character: Node_Key.toCharArray()) {
            // if the path doesn't exist, create a new node.
            root_node.Trie_Children.putIfAbsent(character, new Trie_Node());

            // going to the next node
            root_node = root_node.Trie_Children.get(character);
        }
        root_node.Is_Leaf = true;
    }
    // Searching
    public boolean Searching(String Node_key) {
        System.out.print("Searching the key \"" + Node_key + "\" : ");

        Trie_Node Current_Node = this;

        // repeat
        for (char character: Node_key.toCharArray()) {
            // going to the next node
            Current_Node = Current_Node.Trie_Children.get(character);

            if (Current_Node == null) {
                return false;
            }
        }

        return Current_Node.Is_Leaf;
    }
}

public class Example {
    public static void main (String[] args) {
        // construct a new Trie node
        Trie_Node New_Trie = new Trie_Node();

        New_Trie.Insertion("delft");
        New_Trie.Insertion("delf");
        New_Trie.Insertion("del");

        System.out.println(New_Trie.Searching("del"));            // true
        System.out.println(New_Trie.Searching("delf"));           // true
        System.out.println(New_Trie.Searching("delft"));          // true
        System.out.println(New_Trie.Searching("jiyik"));   // false

        New_Trie.Insertion("jiyik");

        System.out.println(New_Trie.Searching("del"));            // true
        System.out.println(New_Trie.Searching("delf"));           // true
        System.out.println(New_Trie.Searching("delft"));          // true
        System.out.println(New_Trie.Searching("jiyik"));   // true

    }
}

该代码执行相同的工作，但以更节省内存的方式进行。 查看 Java 中 Trie 的输出：

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "jiyik" : false
Inserting the key "jiyik"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "jiyik" : true