The Wypróbuj strukturę danych to drzewiasta struktura danych używana do przechowywania dynamicznego zestawu ciągów znaków. Jest powszechnie stosowany w celu zapewnienia wydajności wyszukiwanie I składowanie kluczy w dużym zbiorze danych. Struktura wspiera operacje takie jak wprowadzenie , szukaj , I usunięcie kluczy, co czyni go cennym narzędziem w takich dziedzinach jak informatyka i wyszukiwanie informacji. W tym artykule zamierzamy to zbadać wstawianie i wyszukiwanie operacja w Trie Data Structure.

Wypróbuj strukturę danych

Spis treści

• Reprezentacja węzła Trie
• Reprezentacja węzła Trie:

  A Wypróbuj strukturę danych składa się z węzłów połączonych krawędziami. Każdy węzeł reprezentuje znak lub część ciągu. Węzeł główny, punkt początkowy Trie, reprezentuje pusty ciąg. Każda krawędź wychodząca z węzła oznacza określony znak. Ścieżka od korzenia do węzła reprezentuje przedrostek ciągu znaków przechowywanego w Trie.

  Prosta struktura reprezentująca węzły alfabetu angielskiego może wyglądać następująco.

  
  
  
  

  matryca lateksowa

  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;  }  } };>

  Jawa

  public 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;  }  } }>

  Przeanalizujmy proces wstawiania słów do struktury danych Trie. Omówiliśmy już podstawy Trie i jego strukturę węzłów.

  jsp

  Oto wizualna reprezentacja wstawiania słów I I NA do struktury danych Trie:

  
  

  
  

  
  

  Wstaw operację w Trie Data Structure

  
  

  Wstawianie i struktura danych Trie:

  przycisk w środku CSS

  • Zacznij od węzła głównego: Z węzłem głównym nie jest powiązany żaden znak Koniec słowa wartosc jest 0 , co oznacza, że ​​w tym miejscu nie kończy się całe słowo.
  • Pierwszy znak a: Oblicz indeks za pomocą „ a’ – ‘a’ = 0 . Sprawdź, czy węzeł podrzędny[0] Jest zero . Ponieważ tak jest, utwórz nowy TrieNode ze znakiem A , Koniec słowa Ustawić 0 i pustą tablicę wskaźników. Przejdź do tego nowego węzła.
  • Drugi znak n: Oblicz wskaźnik za pomocą „n” – „a” = 13 . Sprawdź, czy węzeł podrzędny[13] Jest zero . Tak jest, więc utwórz nowy TrieNode ze znakiem N , Koniec słowa Ustawić 0 i pustą tablicę wskaźników. Przejdź do tego nowego węzła.
  • Trzeci znak d: Oblicz indeks za pomocą „ d’ – ‘a’ = 3 . Sprawdź, czy węzeł podrzędny[3 ] Jest zero . Tak jest, więc utwórz nowy TrieNode ze znakiem D , Koniec słowa Ustawić 1 (wskazując słowo I kończy się tutaj).

  Wstawianie mrówki w strukturze danych Trie:

  • Zacznij od węzła głównego: Węzeł główny nie zawiera żadnych danych, ale śledzi każdy pierwszy znak każdego wstawionego ciągu.
  • Pierwszy znak a: Oblicz indeks za pomocą „ a’ – ‘a’ = 0 . Sprawdź, czy węzeł podrzędny[0] Jest zero . Mamy już A węzeł utworzony z poprzedniego wstawienia. więc przejdź do istniejącego A węzeł.
  • Pierwszy znak n: Oblicz indeks za pomocą „ n’ – ‘a’ = 13 . Sprawdź, czy węzeł podrzędny [13] jest zero . Tak nie jest, więc przejdź do istniejącego N węzeł.
  • Drugi znak t: Oblicz wskaźnik za pomocą „t” – „a” = 19 . Sprawdź, czy węzeł podrzędny [19] jest zero . Tak jest, więc utwórz nowy TrieNode ze znakiem T , Koniec słowa Ustawić 1 (wskazując, że w tym miejscu kończy się słowo mrówka).

  Poniżej znajduje się implementacja wstawiania ciągów znaków w strukturze danych 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) { // Jeśli węzeł dla bieżącego znaku nie istnieje // utwórz nowy węzeł TrieNode* newNode = new TrieNode();  // Zachowaj referencje dla nowo utworzonego // węzła.  currentNode->childNode[c - 'a'] = newNode;  } // Teraz przenieś bieżący wskaźnik węzła do nowo // utworzonego węzła.  currentNode = currentNode->childNode[c - 'a'];  } // Zwiększ wartość słowaEndCount dla ostatniego wskaźnika currentNode //, co oznacza, że ​​istnieje ciąg kończący się na // currentNode.  currentNode->wordEnd = 1; }>

  Złożoność czasowa: O(liczba słów * maxLengthOfWord)
  Przestrzeń pomocnicza: O(liczba słów * maxLengthOfWord)

  Wyszukiwanie klucza w strukturze danych Trie przebiega podobnie do operacji wstawiania. Jednak tylko porównuje postacie i przesuwa się w dół . Wyszukiwanie może zostać zakończone z powodu końca ciągu znaków lub braku klucza w próbie.

  Sposób wyszukiwania krok po kroku w strukturze Trie Data:

  • Zacznij od węzła głównego. To jest punkt wyjścia dla wszystkich wyszukiwań w Trie.
  • Przemierzaj Trie w oparciu o znaki szukanego słowa. Dla każdej postaci podążaj za odpowiednią gałęzią w Trie. Jeśli gałąź nie istnieje, słowo nie występuje w Trie.
  • Jeśli dojdziesz do końca słowa, a flaga wordEnd jest ustawiona na 1, słowo zostało znalezione.
  • Jeśli dojdziesz do końca słowa, a flaga wordEnd ma wartość 0, słowo nie występuje w Trie, mimo że ma taki sam przedrostek jak istniejące słowo.

  Oto wizualna reprezentacja wyszukiwanego słowa tata w strukturze danych Trie:

  Załóżmy, że pomyślnie wprowadziliśmy słowa I , NA , I tata do naszego Trie i musimy wyszukać określone słowa w strukturze danych Trie. Spróbujmy wyszukać to słowo tata :

  
  

  sprawdzenie Java ma wartość null

  

  Operacja wyszukiwania w strukturze danych Trie

  
  

  • Zaczynamy od węzła głównego.
  • Podążamy za gałęzią odpowiadającą literze „d”.
  • Podążamy za gałęzią odpowiadającą znakowi a’.
  • Podążamy za gałęzią odpowiadającą literze „d”.
  • Dochodzimy do końca słowa i Koniec słowa flaga jest 1 . To znaczy że tata jest obecny w Trie.

  Poniżej znajduje się implementacja wyszukiwania ciągów w 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) { // Podane słowo nie istnieje w Trie return false;  } // Przesuń wskaźnik currentNode do już // istniejącego węzła dla bieżącego znaku.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); }>

  Złożoność czasowa: O(liczba słów * maxLengthOfWord)
  Przestrzeń pomocnicza: O(liczba słów * maxLengthOfWord)

  liczba całkowita do łańcucha Java

  Utwórz węzeł główny za pomocą TrieNode() konstruktor.

• Przechowuj kolekcję ciągów, które mają zostać wstawione w próbie, w wektorze ciągów, powiedzmy: przyr .
• Wstawianie wszystkich ciągów w Trie przy pomocy wstaw_klucz() funkcjonować,
• Wyszukaj ciągi znaków za pomocą klucz_wyszukiwania() funkcjonować.

Poniżej implementacja powyższego podejścia:

#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) { // Jeśli węzeł dla bieżącego znaku nie istnieje // utwórz nowy węzeł TrieNode* newNode = new TrieNode();  // Zachowaj referencje dla nowo utworzonego // węzła.  currentNode->childNode[c - 'a'] = newNode;  } // Teraz przenieś bieżący wskaźnik węzła do nowo // utworzonego węzła.  currentNode = currentNode->childNode[c - 'a'];  } // Zwiększ wartość słowaEndCount dla ostatniego wskaźnika currentNode //, co oznacza, że ​​istnieje ciąg kończący się na // currentNode.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Zainicjuj wskaźnik currentNode // za pomocą węzła głównego TrieNode* currentNode = root;  // Wykonaj iterację po długości łańcucha for (auto c : key) { // Sprawdź, czy węzeł istnieje dla bieżącego // znaku w Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // Podane słowo nie istnieje w Trie return false;  } // Przesuń wskaźnik currentNode do już // istniejącego węzła dla bieżącego znaku.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Kod sterownika int main() { // Utwórz węzeł główny dla Trie TrieNode* root = new TrieNode();  // Przechowuje ciągi znaków, które chcemy wstawić do wektora // TrieinputStrings = { 'i', 'mrówka', 'zrób', 'geek', 'tata', 'piłka' };  // liczba operacji wstawiania w Trie int n = inputStrings.size();  for (int i = 0; tj< n; i++) {  insert_key(root, inputStrings[i]);  }  // Stores the strings that we want to search in the Trie  vectorsearchQueryStrings = { 'zrobić', 'geek', 'bat' };  // liczba operacji wyszukiwania w Trie int searchQueries = searchQueryStrings.size();  for (int i = 0; tj< 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; }>

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');  }  }  } }>

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')>

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']; // Wyszukaj każdy ciąg i wypisz, czy został znaleziony w Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Ciąg zapytania występuje w Trie' } else { console.log('Ciąg zapytania nie występuje w Trie' } });>

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>

Spróbuj usunąć

Wyświetlanie zawartości Trie

Funkcja automatycznego uzupełniania za pomocą Trie

Wyszukiwanie wzorców przy użyciu próby wszystkich przyrostków

Problemy praktyczne:

• Minimalne łamanie wyrazów
• Unikalne wiersze w macierzy binarnej
• Liczba odrębnych podciągów
• Słowo Boggle
• Sortowanie tablicy ciągów (lub słów) za pomocą Trie