Java 中的 Trie 資料結構-java教程-PHP中文網

以下文章提供了 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 資料結構