VYZKOUŠEJTE DATOVOU STRUKTURU | VLOŽIT A HLEDAT - TECHCODEVIEW.COM

The Vyzkoušejte datovou strukturu je stromová datová struktura používaná pro ukládání dynamické sady řetězců. Běžně se používá pro efektivní vyhledávání a úložný prostor klíčů ve velké datové sadě. Konstrukce podporuje operace jako např vložení , Vyhledávání , a vymazání klíčů, což z něj činí cenný nástroj v oborech, jako je počítačová věda a vyhledávání informací. V tomto článku budeme zkoumat vkládání a vyhledávání operace v Trie Data Structure.

Vyzkoušejte datovou strukturu

Obsah

Zastoupení Trie Node
Zastoupení Trie Node:
A Vyzkoušejte datovou strukturu sestává z uzlů spojených hranami. Každý uzel představuje znak nebo část řetězce. Kořenový uzel, počáteční bod Trie, představuje prázdný řetězec. Každá hrana vycházející z uzlu znamená specifický znak. Cesta od kořene k uzlu představuje prefix řetězce uloženého v Trie.

Jednoduchá struktura reprezentující uzly anglické abecedy může být následující.

C#
C++struct TrieNode { // pointer array for child nodes of each node TrieNode* childNode[26]; // Used for indicating ending of string bool wordEnd; TrieNode() { // constructor // initialize the wordEnd variable with false // initialize every index of childNode array with // NULL wordEnd = false; for (int i = 0; i < 26; i++) { childNode[i] = NULL; } } };>Jávapublic class TrieNode { // Array for child nodes of each node TrieNode[] childNode; // Used for indicating the end of a string boolean wordEnd; // Constructor public TrieNode() { // Initialize the wordEnd variable with false wordEnd = false; // Initialize every index of the childNode array with null childNode = new TrieNode[26]; for (int i = 0; i < 26; i++) { childNode[i] = null; } } }>
Pojďme si projít proces vkládání slov do datové struktury Trie. Základy Trie a jeho struktury uzlů jsme již probrali.
řetězec formátu java

Zde je vizuální znázornění vkládání slov a a na do datové struktury Tri:
Operace vložení do Trie Data Structure

Vkládání a v datové struktuře Tri:
symetrický rozdíl
- Začněte v kořenovém uzlu: Kořenový uzel nemá s ním spojený žádný znak wordEnd hodnota je 0 , což znamená, že v tomto bodě žádné úplné slovo nekončí.
- První znak A: Vypočítejte index pomocí „ a‘ – ‚a‘ = 0 . Zkontrolujte, zda childNode[0] je nula . Protože je, vytvořte nový TrieNode s postavou A , wordEnd nastaven na 0 a prázdné pole ukazatelů. Přesuňte se do tohoto nového uzlu.
- Druhý znak n: Vypočítejte index pomocí „n“ – „a“ = 13 . Zkontrolujte, zda childNode[13] je nula . Je, takže vytvořte nový TrieNode s postavou n , wordEnd nastaven na 0 a prázdné pole ukazatelů. Přesuňte se do tohoto nového uzlu.
- Třetí znak d: Vypočítejte index pomocí „ d' – „a“ = 3 . Zkontrolujte, zda childNode[3 ] je nula . Je, takže vytvořte nový TrieNode s postavou d , wordEnd nastaven na 1 (označení slova a končí zde).
Vložení mravence do datové struktury Trie:
- Začněte v kořenovém uzlu: Kořenový uzel neobsahuje žádná data, ale sleduje každý první znak každého řetězce, který byl vložen.
- První znak A: Vypočítejte index pomocí „ a‘ – ‚a‘ = 0 . Zkontrolujte, zda childNode[0] je nula . Už máme A uzel vytvořený z předchozího vložení. tak přejít na stávající A uzel.
- První znak n: Vypočítejte index pomocí „ n’ – ‘a’ = 13 . Zkontrolujte, zda childNode [13] je nula . Není, takže přejděte ke stávajícímu n uzel.
- Druhý znak t: Vypočítejte index pomocí „t“ – „a“ = 19 . Zkontrolujte, zda childNode [19] je nula . Je, takže vytvořte nový TrieNode s postavou t , wordEnd nastaven na 1 (s uvedením slova mravenec zde končí).
Níže je uvedena implementace vkládání řetězců do datové struktury Trie:
C++#include using namespace std; struct TrieNode { // pointer array for child nodes of each node TrieNode* childNode[26]; // Used for indicating ending of string bool wordEnd; TrieNode() { // constructor // initialize the wordEnd variable with false // initialize every index of childNode array with // NULL wordEnd = false; for (int i = 0; i < 26; i++) { childNode[i] = NULL; } } }; void insert_key(TrieNode* root, string& key) { // Initialize the currentNode pointer // with the root node TrieNode* currentNode = root; // Iterate across the length of the string for (auto c : key) { // Check if the node exist for the current // character in the Trie. if (currentNode->childNode[c - 'a'] == NULL) { // Pokud uzel pro aktuální znak neexistuje // pak vytvořte nový uzel TrieNode* newNode = new TrieNode(); // Zachovejte odkaz na nově vytvořený // uzel. currentNode->childNode[c - 'a'] = newNode; } // Nyní přesuňte ukazatel aktuálního uzlu na nově // vytvořený uzel. currentNode = currentNode->childNode[c - 'a']; } // Zvyšte počet wordEndCount pro poslední ukazatel currentNode // to znamená, že existuje řetězec končící na // currentNode. currentNode->wordEnd = 1; }>
Časová náročnost: O(počet slov * maxLengthOfWord)
Pomocný prostor: O(počet slov * maxLengthOfWord)
Hledání klíče v datové struktuře Trie je podobné jeho operaci vložení. Nicméně pouze To porovná postavy a posune se dolů . Vyhledávání se může ukončit kvůli konci řetězce nebo nedostatku klíče v trie.

Postupný přístup k vyhledávání ve struktuře Trie Data:
- Začněte u kořenového uzlu. Toto je výchozí bod pro všechna vyhledávání v Trie.
- Projděte Trie na základě znaků slova, které hledáte. U každé postavy následujte odpovídající větev v Trie. Pokud větev neexistuje, slovo není přítomno v Trie.
- Pokud se dostanete na konec slova a příznak wordEnd je nastaven na 1, slovo bylo nalezeno.
- Pokud se dostanete na konec slova a příznak wordEnd je 0, slovo se v Trie nenachází, i když sdílí předponu s existujícím slovem.
Zde je vizuální znázornění hledaného slova Táto v datové struktuře Tri:
Předpokládejme, že jsme slova úspěšně vložili a , na , a Táto do našeho Trie a musíme hledat konkrétní slova v datové struktuře Trie. Zkusme slovo vyhledat Táto :

Vyhledávací operace v datové struktuře Trie
java nahradit znak v řetězci
- Začínáme u kořenového uzlu.
- Sledujeme větev odpovídající znaku ‚d‘.
- Sledujeme větev odpovídající znaku a‘.
- Sledujeme větev odpovídající znaku ‚d‘.
- Dostáváme se na konec slova a wordEnd vlajka je 1 . Tohle znamená tamto Táto je přítomen v Trie.
Níže je implementace vyhledávacích řetězců v Trie Data Structure:
C++#include using namespace std; struct TrieNode { // pointer array for child nodes of each node TrieNode* childNode[26]; // Used for indicating ending of string bool wordEnd; TrieNode() { // constructor // initialize the wordEnd variable with false // initialize every index of childNode array with // NULL wordEnd = false; for (int i = 0; i < 26; i++) { childNode[i] = NULL; } } }; bool search_key(TrieNode* root, string& key) { // Initialize the currentNode pointer // with the root node TrieNode* currentNode = root; // Iterate across the length of the string for (auto c : key) { // Check if the node exist for the current // character in the Trie. if (currentNode->childNode[c - 'a'] == NULL) { // Dané slovo v Trie neexistuje return false; } // Přesune ukazatel currentNode na již // existující uzel pro aktuální znak. currentNode = currentNode->childNode[c - 'a']; } return (currentNode->wordEnd == true); }>
Časová náročnost: O(počet slov * maxLengthOfWord)
Pomocný prostor: O(počet slov * maxLengthOfWord)
celé číslo na řetězec java
Vytvořte kořenový uzel s pomocí TrieNode() konstruktér.
Uložte kolekci řetězců, které je třeba vložit do trie, do vektoru řetězců, řekněme, arr .
Vložení všech řetězců do Trie s pomocí insert_key() funkce,
Hledejte řetězce s pomocí vyhledávací_klíč() funkce.

Níže je uvedena implementace výše uvedeného přístupu:

C++

 #include  using namespace std; struct TrieNode {  // pointer array for child nodes of each node  TrieNode* childNode[26];  // Used for indicating ending of string  bool wordEnd;  TrieNode()  {  // constructor  // initialize the wordEnd variable with false  // initialize every index of childNode array with  // NULL  wordEnd = false;  for (int i = 0; i < 26; i++) {  childNode[i] = NULL;  }  } }; void insert_key(TrieNode* root, string& key) {  // Initialize the currentNode pointer  // with the root node  TrieNode* currentNode = root;  // Iterate across the length of the string  for (auto c : key) {  // Check if the node exist for the current  // character in the Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // Pokud uzel pro aktuální znak neexistuje // pak vytvořte nový uzel TrieNode* newNode = new TrieNode();  // Zachovejte odkaz na nově vytvořený // uzel.  currentNode->childNode[c - 'a'] = newNode;  } // Nyní přesuňte ukazatel aktuálního uzlu na nově // vytvořený uzel.  currentNode = currentNode->childNode[c - 'a'];  } // Zvyšte počet wordEndCount pro poslední ukazatel currentNode // to znamená, že existuje řetězec končící na // currentNode.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Inicializace ukazatele currentNode // s kořenovým uzlem TrieNode* currentNode = root;  // Iterace po délce řetězce for (auto c : key) { // Zkontrolujte, zda existuje uzel pro aktuální znak // v Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // Dané slovo v Trie neexistuje return false;  } // Přesune ukazatel currentNode na již // existující uzel pro aktuální znak.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Kód ovladače int main() { // Vytvoří kořenový uzel pro Trie TrieNode* root = new TrieNode();  // Uloží řetězce, které chceme vložit do vektoru // TrieinputStrings = { 'and', 'ant', 'do', 'geek', 'táta', 'koule' };  // počet operací vložení v Trie int n = inputStrings.size();  for (int i = 0; i< n; i++) {  insert_key(root, inputStrings[i]);  }  // Stores the strings that we want to search in the Trie  vectorsearchQueryStrings = { 'do', 'geek', 'bat' };  // počet vyhledávacích operací v Trie int searchQueries = searchQueryStrings.size();  for (int i = 0; i< searchQueries; i++) {  cout << 'Query String: ' << searchQueryStrings[i]  << '
';  if (search_key(root, searchQueryStrings[i])) {  // the queryString is present in the Trie  cout << 'The query string is present in the '  'Trie
';  }  else {  // the queryString is not present in the Trie  cout << 'The query string is not present in '  'the Trie
';  }  }  return 0; }>

Jáva

 class TrieNode {  TrieNode[] childNode;  boolean wordEnd;  TrieNode()  {  childNode = new TrieNode[26];  wordEnd = false;  } } class Trie {  TrieNode root;  Trie() { root = new TrieNode(); }  // Function to insert a key into the Trie  void insert(String key)  {  TrieNode currentNode = root;  for (int i = 0; i < key.length(); i++) {  int index = key.charAt(i) - 'a';  if (currentNode.childNode[index] == null) {  currentNode.childNode[index]  = new TrieNode();  }  currentNode = currentNode.childNode[index];  }  currentNode.wordEnd = true;  }  // Function to search for a key in the Trie  boolean search(String key)  {  TrieNode currentNode = root;  for (int i = 0; i < key.length(); i++) {  int index = key.charAt(i) - 'a';  if (currentNode.childNode[index] == null) {  return false;  }  currentNode = currentNode.childNode[index];  }  return currentNode.wordEnd;  } } public class Main {  public static void main(String[] args)  {  Trie trie = new Trie();  String[] inputStrings  = { 'and', 'ant', 'do', 'geek', 'dad', 'ball' };  // Insert each string into the Trie  for (String str : inputStrings) {  trie.insert(str);  }  String[] searchQueryStrings  = { 'do', 'geek', 'bat' };  // Search for each string and print whether it is  // found in the Trie  for (String query : searchQueryStrings) {  System.out.println('Query String: ' + query);  if (trie.search(query)) {  System.out.println(  'The query string is present in the Trie');  }  else {  System.out.println(  'The query string is not present in the Trie');  }  }  } }>

Krajta

 class TrieNode: def __init__(self): self.childNode = [None] * 26 self.wordEnd = False class Trie: def __init__(self): self.root = TrieNode() # Function to insert a key into the Trie def insert(self, key): currentNode = self.root for char in key: index = ord(char) - ord('a') if not currentNode.childNode[index]: currentNode.childNode[index] = TrieNode() currentNode = currentNode.childNode[index] currentNode.wordEnd = True # Function to search for a key in the Trie def search(self, key): currentNode = self.root for char in key: index = ord(char) - ord('a') if not currentNode.childNode[index]: return False currentNode = currentNode.childNode[index] return currentNode.wordEnd if __name__ == '__main__': trie = Trie() inputStrings = ['and', 'ant', 'do', 'geek', 'dad', 'ball'] # Insert each string into the Trie for word in inputStrings: trie.insert(word) searchQueryStrings = ['do', 'geek', 'bat'] # Search for each string and print whether it is found in the Trie for query in searchQueryStrings: print('Query String:', query) if trie.search(query): print('The query string is present in the Trie') else: print('The query string is not present in the Trie')>

JavaScript

 class TrieNode {  constructor() {  // Initialize the childNode array with 26 nulls  this.childNode = Array(26).fill(null);  // Initialize wordEnd to the false indicating that no word ends here yet  this.wordEnd = false;  } } class Trie {  constructor() {  // Initialize the root node of the Trie  this.root = new TrieNode();  }  // Function to insert a key into the Trie  insert(key) {  // Start from the root node  let currentNode = this.root;  for (let i = 0; i < key.length; i++) {  const index = key.charCodeAt(i) - 'a'.charCodeAt(0);  if (currentNode.childNode[index] === null) {  currentNode.childNode[index] = new TrieNode();  }  // Move to the next node in the Trie  currentNode = currentNode.childNode[index];  }  // Mark the end of the word  currentNode.wordEnd = true;  }  // Function to search for a key in the Trie  search(key) {  // Start from the root node  let currentNode = this.root;  // Iterate through each character in the key  for (let i = 0; i < key.length; i++) {  const index = key.charCodeAt(i) - 'a'.charCodeAt(0);  if (currentNode.childNode[index] === null) {  return false;  }  // Move to the next node in the Trie  currentNode = currentNode.childNode[index];  }  // Return true if the end of the word is marked otherwise false  return currentNode.wordEnd;  } } // Driver code const trie = new Trie(); const inputStrings = ['and', 'ant', 'do', 'geek', 'dad', 'ball']; // Insert each string into the Trie inputStrings.forEach((str) =>trie.insert(str)); const searchQueryStrings = ['do', 'geek', 'bat']; // Vyhledejte každý řetězec a vytiskněte, zda byl nalezen v Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Řetězec dotazu je přítomen v Trie' } else { console.log('Řetězec dotazu není přítomen v Trie' } });>

Výstup

Query String: do The query string is present in the Trie Query String: geek The query string is present in the Trie Query String: bat The query string is not present in the Trie>

Zkuste Smazat
Zobrazení obsahu Trie
Funkce automatického dokončování pomocí Trie
Hledání vzoru pomocí Trie všech přípon
Problémy s praxí:

Minimální zalomení slov
Jedinečné řádky v binární matici
Počet různých podřetězců
Slovo Boggle
Třídění pole řetězců (nebo slov) pomocí Trie

TechCodeview

Vyzkoušejte datovou strukturu | Vložit a hledat

Vytvořte kořenový uzel s pomocí TrieNode() konstruktér.