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; } } };>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:
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; } 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; }> Jawa 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'); } } } }> Pyton 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']; // 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' } });> Wyjście
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ąć
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