Trie es una estructura de datos de recuperación de información eficiente. Con Trie, las complejidades de búsqueda se pueden llevar a un límite óptimo (longitud de clave).
La tarea es buscar una string en un Trie usando recursividad.
Ejemplos:
root / \ t a | | h n | | \ e s y / | | i r w | | | r e e | r Input : str = "anywhere" Output : not found Input : str = "answer" Output : found
Enfoque:
buscar una clave es similar a la operación de inserción , sin embargo, solo comparamos los caracteres y nos movemos hacia abajo. La búsqueda puede terminar debido al final de una string o falta de clave en el trie. En el primer caso, si el campo endOfWord del último Node es verdadero, entonces la clave existe en el trie. En el segundo caso, la búsqueda termina sin examinar todos los caracteres de la clave, ya que la clave no está presente en el trie.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to search in a trie #include <bits/stdc++.h> using namespace std; #define CHILDREN 26 #define MAX 100 // Trie node struct trie { trie* child[CHILDREN]; // endOfWord is true if the node represents // end of a word bool endOfWord; }; // Function will return the new node(initialized to NULLs) trie* createNode() { trie* temp = new trie(); temp->endOfWord = false; for (int i = 0; i < CHILDREN; i++) { // initially assign null to the all child temp->child[i] = NULL; } return temp; } /*function will insert the string in a trie recursively*/ void insertRecursively(trie* itr, string str, int i) { if (i < str.length()) { int index = str[i] - 'a'; if (itr->child[index] == NULL) { // Insert a new node itr->child[index] = createNode(); } // Recursive call for insertion of a string insertRecursively(itr->child[index], str, i + 1); } else { // Make the endOfWord true which represents // the end of string itr->endOfWord = true; } } // Function call to insert a string void insert(trie* itr, string str) { // Function call with necessary arguments insertRecursively(itr, str, 0); } // Function to search the string in a trie recursively bool searchRecursively(trie* itr, char str[], int i, int len) { // When a string or any character // of a string is not found if (itr == NULL) return false; // Condition of finding string successfully if (itr->endOfWord == true && i == len - 1) { // Return true when endOfWord // of last node containes true return true; } int index = str[i] - 'a'; // Recursive call and return // value of function call stack return searchRecursively(itr->child[index], str, i + 1, len); } // Function call to search the string void search(trie* root, string str) { char arr[str.length() + 1]; strcpy(arr, str.c_str()); // If string found if (searchRecursively(root, arr, 0, str.length() + 1)) cout << "found" << endl; else { cout << "not found" << endl; } } // Driver code int main() { trie* root = createNode(); // Function call to insert the string insert(root, "their"); insert(root, "there"); insert(root, "answer"); insert(root, "any"); // Function call to search the string search(root, "anywhere"); search(root, "answer"); return 0; }
Java
// Java program to search in a trie import java.util.*; public class Main { static int CHILDREN = 26; // Trie node static class trie { public boolean endOfWord; public trie[] child; public trie() { endOfWord = false; // endOfWord is true if the node represents // end of a word child = new trie[CHILDREN]; } } // Function will return the new node(initialized to NULLs) static trie createNode() { trie temp = new trie(); temp.endOfWord = false; for (int i = 0; i < CHILDREN; i++) { // Initialise all child to the null, initially temp.child[i] = null; } // Return newly created node return temp; } // Function will insert the string in a trie recursively static void insertRecursively(trie itr, String str, int i) { if (i < str.length()) { int index = str.charAt(i) - 'a'; if (itr.child[index] == null) { // Assigning a newly created node itr.child[index] = createNode(); } // Recursive call for insertion // of a string in a trie insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true which represents // the end of string itr.endOfWord = true; } } // Function call to insert a string static void insert(trie itr, String str) { // Function call with necessary arguments insertRecursively(itr, str, 0); } // Function to search the string in a trie recursively static boolean searchRecursively(trie itr, char[] str, int i, int len) { // When a string or any character // of a string is not found if (itr == null) return false; // Condition of finding string successfully if (itr.endOfWord == true && i == len - 1) { // Return true when endOfWord // of last node containes true return true; } int index = str[i] - 'a'; // Recursive call and return // value of function call stack return searchRecursively(itr.child[index], str, i + 1, len); } // Function call to search the string static void search(trie root, String str) { char[] arr = new char[str.length() + 1]; for(int i = 0; i < str.length(); i++) { arr[i] = str.charAt(i); } // If string found if (searchRecursively(root, arr, 0, str.length() + 1)) System.out.println("found"); else { System.out.println("not found"); } } public static void main(String[] args) { trie root = createNode(); // Function call to insert the string insert(root, "their"); insert(root, "there"); insert(root, "answer"); insert(root, "any"); // Function call to search the string search(root, "anywhere"); search(root, "answer"); } } // This code is contributed by suresh07.
Python3
# Python3 program to traverse in bottom up manner CHILDREN = 26 MAX = 100 # Trie node class trie: def __init__(self): self.child = [None for i in range(CHILDREN)] # endOfWord is true if the node represents # end of a word self.endOfWord = False # Function will return the new node(initialized to NULLs) def createNode(): temp = trie() return temp # Function will insert the string in a trie recursively def insertRecursively(itr, str, i): if(i < len(str)): index = ord(str[i]) - ord('a') if(itr.child[index] == None ): # Insert a new node itr.child[index] = createNode(); # Recursive call for insertion of string insertRecursively(itr.child[index], str, i + 1); else: # Make the endOfWord true which represents # the end of string itr.endOfWord = True; # Function call to insert a string def insert(itr, str): # Function call with necessary arguments insertRecursively(itr, str, 0); # Function to search the string in a trie recursively def searchRecursively(itr ,str, i, len): # When a string or any character # of a string is not found if (itr == None): return False # Condition of finding string successfully if (itr.endOfWord == True and i == len - 1): # Return true when endOfWord # of last node containes true return True index = ord(str[i]) - ord('a') # Recursive call and return # value of function call stack return searchRecursively(itr.child[index], str, i + 1, len) # Function call to search the string def search(root, str): arr = ['' for i in range(len(str) + 1)] arr = str # If string found if (searchRecursively(root, arr, 0, len(str) + 1)): print("found") else: print("not found") # Driver code if __name__=='__main__': root = createNode(); # Function call to insert the string insert(root, "their"); insert(root, "there"); insert(root, "answer"); insert(root, "any"); # Function call to search the string search(root, "anywhere") search(root, "answer") # This code is contributed by rutvik_56
C#
// C# program to search in a trie using System; class GFG { static int CHILDREN = 26; // Trie node class trie { public bool endOfWord; public trie[] child; public trie() { endOfWord = false; // endOfWord is true if the node represents // end of a word child = new trie[CHILDREN]; } } // Function will return the new node(initialized to NULLs) static trie createNode() { trie temp = new trie(); temp.endOfWord = false; for (int i = 0; i < CHILDREN; i++) { // Initialise all child to the null, initially temp.child[i] = null; } // Return newly created node return temp; } // Function will insert the string in a trie recursively static void insertRecursively(trie itr, string str, int i) { if (i < str.Length) { int index = str[i] - 'a'; if (itr.child[index] == null) { // Assigning a newly created node itr.child[index] = createNode(); } // Recursive call for insertion // of a string in a trie insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true which represents // the end of string itr.endOfWord = true; } } // Function call to insert a string static void insert(trie itr, string str) { // Function call with necessary arguments insertRecursively(itr, str, 0); } // Function to search the string in a trie recursively static bool searchRecursively(trie itr, char[] str, int i, int len) { // When a string or any character // of a string is not found if (itr == null) return false; // Condition of finding string successfully if (itr.endOfWord == true && i == len - 1) { // Return true when endOfWord // of last node containes true return true; } int index = str[i] - 'a'; // Recursive call and return // value of function call stack return searchRecursively(itr.child[index], str, i + 1, len); } // Function call to search the string static void search(trie root, string str) { char[] arr = new char[str.Length + 1]; for(int i = 0; i < str.Length; i++) { arr[i] = str[i]; } // If string found if (searchRecursively(root, arr, 0, str.Length + 1)) Console.WriteLine("found"); else { Console.WriteLine("not found"); } } static void Main() { trie root = createNode(); // Function call to insert the string insert(root, "their"); insert(root, "there"); insert(root, "answer"); insert(root, "any"); // Function call to search the string search(root, "anywhere"); search(root, "answer"); } } // This code is contributed by mukesh07.
Javascript
<script> // Javascript program to search in a trie let CHILDREN = 26; // Trie node class trie { constructor() { this.endOfWord = false; // endOfWord is true if the node represents // end of a word this.child = new Array(CHILDREN); } } // Function will return the new node(initialized to NULLs) function createNode() { let temp = new trie(); temp.endOfWord = false; for (let i = 0; i < CHILDREN; i++) { // Initialise all child to the null, initially temp.child[i] = null; } // Return newly created node return temp; } // Function will insert the string in a trie recursively function insertRecursively(itr, str, i) { if (i < str.length) { let index = str[i] - 'a'; if (itr.child[index] == null) { // Assigning a newly created node itr.child[index] = createNode(); } // Recursive call for insertion // of a string in a trie insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true which represents // the end of string itr.endOfWord = true; } } // Function call to insert a string function insert(itr, str) { // Function call with necessary arguments insertRecursively(itr, str, 0); } // Function to search the string in a trie recursively function searchRecursively(itr, str, i, len) { // When a string or any character // of a string is not found if (itr == null) return false; // Condition of finding string successfully if (itr.endOfWord == true && i == len - 1) { // Return true when endOfWord // of last node containes true return true; } let index = str[i] - 'a'; // Recursive call and return // value of function call stack return searchRecursively(itr.child[index], str, i + 1, len); } // Function call to search the string function search(root, str) { let arr = new Array(str.length + 1); for(let i = 0; i < str.length; i++) { arr[i] = str[i]; } // If string found if (searchRecursively(root, arr, 0, str.length + 1)) document.write("found" + "</br>"); else { document.write("not found" + "</br>"); } } let root = createNode(); // Function call to insert the string insert(root, "their"); insert(root, "there"); insert(root, "answer"); insert(root, "any"); // Function call to search the string search(root, "anywhere"); search(root, "answer"); // This code is contributed by divyeshrabadiya07. </script>
not found found
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA