Det Prøv datastruktur er en trælignende datastruktur, der bruges til lagring af et dynamisk sæt strenge. Det er almindeligt anvendt til effektiv hentning og opbevaring af nøgler i et stort datasæt. Strukturen understøtter operationer som f.eks indskud , Søg , og sletning af nøgler, hvilket gør det til et værdifuldt værktøj inden for områder som datalogi og informationssøgning. I denne artikel skal vi udforske indsættelse og søgning drift i Trie Data Structure.
Prøv datastruktur
Indholdsfortegnelse
- Repræsentation af af Trie Node
- Repræsentation af Trie Node:
EN Prøv datastruktur består af noder forbundet med kanter. Hver node repræsenterer et tegn eller en del af en streng. Rodnoden, startpunktet for Trie, repræsenterer en tom streng. Hver kant, der udgår fra en node, betegner en bestemt karakter. Stien fra roden til en node repræsenterer præfikset for en streng gemt i Trie.
En simpel struktur til at repræsentere noder i det engelske alfabet kan være som følger.
linux tastaturgenveje
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; } } }>Lad os gå gennem processen med at indsætte ordene i en Trie-datastruktur. Vi har allerede dækket det grundlæggende i Trie og dets nodestruktur.
10 ml til ounces
Her er en visuel repræsentation af indsættelse af ordene og og på ind i en Trie-datastruktur:
Indsæt operation i Trie Data Structure
Indsættelse og i Trie datastruktur:
hvad betyder xdxd
- Start ved rodnoden: Rodknuden har ingen karakter forbundet med den og dens ordslut værdi er 0 , hvilket indikerer, at intet fuldstændigt ord slutter på dette tidspunkt.
- Første tegn a: Beregn indekset ved at bruge ' a' – 'a' = 0 . Tjek om childNode[0] er nul . Da det er, skal du oprette en ny TrieNode med karakteren -en , ordslut indstillet til 0 , og en tom række af pointere. Flyt til denne nye node.
- Andet tegn n: Beregn indekset vha 'n' – 'a' = 13 . Tjek evt childNode[13] er nul . Det er det, så opret en ny TrieNode med karakteren n , ordslut indstillet til 0 , og en tom række af pointere. Flyt til denne nye node.
- Tredje tegn d: Beregn indekset ved at bruge ' d' – 'a' = 3 . Tjek evt childNode[3 ] er nul . Det er det, så opret en ny TrieNode med karakteren d , ordslut indstillet til 1 (angiver ordet og slutter her).
Indsættelse af myre i Trie datastruktur:
- Start ved rodnoden: Rodnoden indeholder ingen data, men den holder styr på hvert første tegn i hver streng, der er blevet indsat.
- Første tegn a: Beregn indekset ved at bruge ' a' – 'a' = 0 . Tjek om childNode[0] er nul . Vi har allerede -en node oprettet fra den forrige indsættelse. så flyt til det eksisterende -en node.
- Første tegn n: Beregn indekset ved at bruge ' n' – 'a' = 13 . Tjek evt barnNode [13] er nul . Det er det ikke, så flyt til det eksisterende n node.
- Andet tegn t: Beregn indekset vha 't' – 'a' = 19 . Tjek evt barnNode [19] er nul . Det er det, så opret en ny TrieNode med karakteren t , ordslut indstillet til 1 (angiver ordet myre ender her).
Nedenfor er implementeringen af indsættelse af strenge i Trie datastruktur:
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) { // Hvis node for nuværende karakter ikke findes // så lav en ny node TrieNode* newNode = new TrieNode(); // Behold referencen for den nyoprettede // node. currentNode->childNode[c - 'a'] = nyNode; } // Flyt nu den aktuelle nodemarkør til den nyoprettede node. currentNode = currentNode->childNode[c - 'a']; } // Forøg wordEndCount for den sidste currentNode // pointer dette antyder, at der er en streng, der ender på // currentNode. currentNode->wordEnd = 1; }>Tidskompleksitet: O(antal ord * maxLengthOfWord)
Hjælpeplads: O(antal ord * maxLengthOfWord)Søgning efter en nøgle i Trie-datastrukturen ligner dens indsættelsesoperation. Dog kun det sammenligner karaktererne og rykker ned . Søgningen kan afsluttes på grund af slutningen af en streng eller manglende nøgle i forsøget.
Trin for trin tilgang til søgning i Trie Data struktur:
freddie mercury
- Start ved rodnoden. Dette er udgangspunktet for alle søgninger i Trie.
- Gennemse Trie baseret på tegnene i det ord, du søger efter. For hver karakter skal du følge den tilsvarende gren i Trie. Hvis grenen ikke eksisterer, er ordet ikke til stede i Trie.
- Hvis du når til slutningen af ordet, og ordet End-flag er sat til 1, er ordet fundet.
- Hvis du når til slutningen af ordet, og ordet End-flag er 0, er ordet ikke til stede i Trie, selvom det deler et præfiks med et eksisterende ord.
Her er en visuel repræsentation af søgeord far i Trie datastruktur:
Lad os antage, at vi med succes har indsat ordene og , på , og far ind i vores Trie, og vi skal søge efter specifikke ord i Trie-datastrukturen. Lad os prøve at søge efter ordet far :
Søgeoperation i Trie Data Structure
- Vi starter ved rodknuden.
- Vi følger den gren, der svarer til tegnet 'd'.
- Vi følger den gren, der svarer til tegnet a'.
- Vi følger den gren, der svarer til tegnet 'd'.
- Vi når slutningen af ordet og ordslut flag er 1 . Det betyder at far er til stede i Trie.
Nedenfor er implementeringen af søgestrenge i 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) { // Givet ord findes ikke i Trie return false; } // Flyt den aktuelle node-markør til den allerede // eksisterende node for det aktuelle tegn. currentNode = currentNode->childNode[c - 'a']; } return (currentNode->wordEnd == sand); }>Tidskompleksitet: O(antal ord * maxLengthOfWord)
Hjælpeplads: O(antal ord * maxLengthOfWord)heltal til streng java
Opret en rodnode ved hjælp af TrieNode() konstruktør.
- Gem en samling af strenge, der skal indsættes i prøven i en vektor af strenge, f.eks. arr .
- Indsættelse af alle strenge i Trie ved hjælp af indsæt_nøgle() fungere,
- Søgestrenge ved hjælp af søge_nøgle() fungere.
Nedenfor er implementeringen af ovenstående tilgang:
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) { // Hvis node for nuværende karakter ikke findes // så lav en ny node TrieNode* newNode = new TrieNode(); // Behold referencen for den nyoprettede // node. currentNode->childNode[c - 'a'] = nyNode; } // Flyt nu den aktuelle nodemarkør til den nyoprettede node. currentNode = currentNode->childNode[c - 'a']; } // Forøg wordEndCount for den sidste currentNode // pointer dette antyder, at der er en streng, der ender på // currentNode. currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Initialiser den aktuelleNode-markør // med rodnoden TrieNode* currentNode = root; // Iterér på tværs af længden af strengen for (auto c : key) { // Tjek om noden eksisterer for det aktuelle //-tegn i prøven. if (currentNode->childNode[c - 'a'] == NULL) { // Givet ord findes ikke i Trie return false; } // Flyt den aktuelle node-markør til den allerede // eksisterende node for det aktuelle tegn. currentNode = currentNode->childNode[c - 'a']; } return (currentNode->wordEnd == sand); } // Driverkode int main() { // Lav en rodnode for Trie TrieNode* root = new TrieNode(); // Gemmer de strenge, som vi ønsker at indsætte i // Prøv vektoreninputStrings = { 'og', 'ant', 'do', 'nørd', 'far', 'bold' }; // antal indsættelsesoperationer i 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' }; // antal søgeoperationer i 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; }> Java 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'); } } } }> Python 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', 'nørd', 'bat']; // Søg efter hver streng, og udskriv, om den findes i Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Forespørgselsstrengen er til stede i Trie'); } else { console.log('Forespørgselsstrengen er ikke til stede i Trie');> Produktion
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>
Prøv at slette
Øvelsesproblemer:
- Minimum Word Break
- Unikke rækker i en binær matrix
- Antal distinkte understrenge
- Ord Boggle
- Sortering af række af strenge (eller ord) ved hjælp af Trie