Java 中的 Trie 数据结构-java教程-PHP中文网

Java 中的 Trie 数据结构

王林

发布： 2024-08-30 16:19:11

原创

532 人浏览过

以下文章提供了 Java 中的 Trie 数据结构的概述。基本上，数据结构在计算机编程中起着非常重要的作用，而且我们必须知道何时以及为什么在计算机编程中使用不同类型的数据结构。通常trie是一种离散的数据结构，这个不太熟悉，或者可以说这不是一个广泛使用的数据结构，而是在典型的算法中使用的，trie也称为数字树；它还有另一个名称，即基数或前缀。

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

使用 trie 数据结构，我们通过带有键的结构良好的树中的前缀来搜索元素，并且存储字符串是有利的。此外，我们还可以对 trie 数据结构执行不同的操作，例如插入、删除和搜索。

Java 中 Trie 数据结构的语法

下面给出的是提到的语法：

public void insert_node(specified string of word){
TrieNode present = rootNode;
For (char i: word.toCharArray()){
Present = present.getChildren().computeIfAbsent(I, c->new TrieNode());
}
Present.setEndOfWord(true)
}

登录后复制

说明：

通过使用上面的语法，我们尝试将元素插入到 trie 数据结构中；为此，我们需要执行以下步骤：

首先，我们需要将当前节点设置为根节点，进行插入操作。
之后，我们需要将当前字符设置为单词的第一个字符。
如果数字树中存在当前节点，则引用当前字符，如果当前节点不存在，则需要创建新节点。
最后我们可以使用Trie键进行数字遍历了。

类似地，我们可以编写删除和搜索操作的语法。

Trie 数据结构在 Java 中如何工作？

下面显示了 trie 数据结构在 java 中的工作原理：

通常我们可以在 trie 数据结构中执行 3 种不同的操作，如下所示：

1.插入元素操作

上面我们已经解释了java中插入操作是如何工作的。插入操作的复杂度为O(n)，其中n代表key的大小。

2.求元素操作

插入操作后，我们可以使用如下算法对trie数据结构进行搜索或查找操作。

代码：

public void find_node(specified string of word){
TrieNode present = rootNode;
For (char j = 0; j < word.length(); j++){
char c = word.charAt(j);
TrieNode node = present.getChildren().get(c);
If (node = = null){
return false;
}
Present = node;
}
return present.isEndOfWord();
}

登录后复制

说明：

现在对 trie 数据结构中的搜索元素执行以下步骤，如下所示：

首先，从根节点获取子节点。
之后我们需要迭代字符串中的每个字符。
现在检查指定的字符是否存在，或者我们可以说它是子特里树的一部分；如果指定的字符不是 sub trie 的一部分，则返回 false 并退出。
重复第二步和第三步，直到字符串中没有字符。
插入操作的复杂度为O(n)，其中n代表key的大小。

3.删除元素操作

除了插入操作和查找元素之外；显然，我们同样应该有删除操作的选项，所以我们需要按照以下步骤操作。

检查指定元素现在是否是 trie 的一部分。
如果找到该元素，请将其从 trie 中删除。
此计算的复杂度为 O(n)，其中 n 表示密钥的长度。

Java 中的 Trie 数据结构示例

下面是 Java 中 Trie 数据结构的示例：

代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// created class to store node into the trie data structure
class trie_data
{
// Define the size of alphabet size
private static final int CHAR_AlPHA_SIZE = 26;
private boolean isLeaf;
private List<trie_data> child = null;
// Created Constructor of class
trie_data()
{
isLeaf = false;
child = new ArrayList<>(Collections.nCopies(CHAR_AlPHA_SIZE, null));
}
// function for insertion operation
public void trie_insert(String id)
{
System.out.println("We inserted new element into the data structure \"" + id + "\"");
// Staritng from the parent node that is root node
trie_data present = this;
for (char ch: id.toCharArray())
{
// if node is not exist then create new node in trie
if (present.child.get(ch - 'a') == null) {
present.child.set(ch - 'a', new trie_data());
}
// visit next node
present = present.child.get(ch - 'a');
}
// mark present as leaf node
present.isLeaf = true;
}
// search function to search element into trie data structure
// if key value is not present then it return the false
public boolean trie_search(String id)
{
System.out.print("We searched element\"" + id + "\" : ");
trie_data present = this;
for (char ch: id.toCharArray())
{
// visit next node
present = present.child.get(ch - 'a');
if (present == null) {
return false;
}
}
return present.isLeaf;
}
}
class Main
{
public static void main (String[] args)
{
// construct a new Trie node
trie_data head = new trie_data();
head.trie_insert("the");
head.trie_insert("they");
head.trie_insert("final");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // false
head.trie_insert("Sample");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // true
}
}

登录后复制

说明：

在上面的例子中，我们尝试用java实现trie数据结构，这里首先我们创建了一个类来将节点存储到trie数据结构中。然后，我们使用 CHAR_AlPHA_SIZE 定义字母表大小。然后，我们为该类创建了一个构造函数。
有一个函数用于插入操作'trie_insert'()以及从trie数据结构中搜索元素，如上面的程序所示。在程序的最后，我们只需调用插入和搜索函数，并使用我们需要在 trie 数据结构中插入和搜索的不同值即可。

输出：

Java 中的 Trie 数据结构