prueba | (Insertar y Buscar)

 

Trie es una estructura de datos de recuperación de información eficiente. Con Trie, las complejidades de búsqueda se pueden llevar al límite óptimo (longitud de clave). Si almacenamos claves en un árbol de búsqueda binario, un BST bien balanceado necesitará un tiempo proporcional a M * log N , donde M es la longitud máxima de la string y N es el número de claves en el árbol. Usando Trie, podemos buscar la clave en tiempo O(M). Sin embargo, la sanción se aplica a los requisitos de almacenamiento de Trie (consulte Aplicaciones de Trie para obtener más detalles)
 

C++

// C++ implementation of search and insert
// operations on Trie
#include <bits/stdc++.h>
using namespace std;
  
const int ALPHABET_SIZE = 26;
  
// trie node
struct TrieNode
{
    struct TrieNode *children[ALPHABET_SIZE];
  
    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};
  
// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void)
{
    struct TrieNode *pNode =  new TrieNode;
  
    pNode->isEndOfWord = false;
  
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
  
    return pNode;
}
  
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
  
    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
  
        pCrawl = pCrawl->children[index];
    }
  
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
  
// Returns true if key presents in trie, else
// false
bool search(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
  
    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return false;
  
        pCrawl = pCrawl->children[index];
    }
  
    return (pCrawl->isEndOfWord);
}
  
// Driver
int main()
{
    // Input keys (use only 'a' through 'z'
    // and lower case)
    string keys[] = {"the", "a", "there",
                    "answer", "any", "by",
                     "bye", "their" };
    int n = sizeof(keys)/sizeof(keys[0]);
  
    struct TrieNode *root = getNode();
  
    // Construct trie
    for (int i = 0; i < n; i++)
        insert(root, keys[i]);
  
    // Search for different keys
    search(root, "the")? cout << "Yes\n" :
                         cout << "No\n";
    search(root, "these")? cout << "Yes\n" :
                           cout << "No\n";
    search(root, "their")? cout << "Yes\n" :
                         cout << "No\n";
    search(root, "thaw")? cout << "Yes\n" :
                           cout << "No\n";
    return 0;
}

C

// C implementation of search and insert operations
// on Trie
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
  
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
  
// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
  
// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
  
// trie node
struct TrieNode
{
    struct TrieNode *children[ALPHABET_SIZE];
  
    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};
  
// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void)
{
    struct TrieNode *pNode = NULL;
  
    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
  
    if (pNode)
    {
        int i;
  
        pNode->isEndOfWord = false;
  
        for (i = 0; i < ALPHABET_SIZE; i++)
            pNode->children[i] = NULL;
    }
  
    return pNode;
}
  
// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(struct TrieNode *root, const char *key)
{
    int level;
    int length = strlen(key);
    int index;
  
    struct TrieNode *pCrawl = root;
  
    for (level = 0; level < length; level++)
    {
        index = CHAR_TO_INDEX(key[level]);
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
  
        pCrawl = pCrawl->children[index];
    }
  
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
  
// Returns true if key presents in trie, else false
bool search(struct TrieNode *root, const char *key)
{
    int level;
    int length = strlen(key);
    int index;
    struct TrieNode *pCrawl = root;
  
    for (level = 0; level < length; level++)
    {
        index = CHAR_TO_INDEX(key[level]);
  
        if (!pCrawl->children[index])
            return false;
  
        pCrawl = pCrawl->children[index];
    }
  
    return (pCrawl->isEndOfWord);
}
  
// Driver
int main()
{
    // Input keys (use only 'a' through 'z' and lower case)
    char keys[][8] = {"the", "a", "there", "answer", "any",
                     "by", "bye", "their"};
  
    char output[][32] = {"Not present in trie", "Present in trie"};
  
  
    struct TrieNode *root = getNode();
  
    // Construct trie
    int i;
    for (i = 0; i < ARRAY_SIZE(keys); i++)
        insert(root, keys[i]);
  
    // Search for different keys
    printf("%s --- %s\n", "the", output[search(root, "the")] );
    printf("%s --- %s\n", "these", output[search(root, "these")] );
    printf("%s --- %s\n", "their", output[search(root, "their")] );
    printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );
  
    return 0;
}

Java

// Java implementation of search and insert operations
// on Trie
public class Trie {
      
    // Alphabet size (# of symbols)
    static final int ALPHABET_SIZE = 26;
      
    // trie node
    static class TrieNode
    {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
       
        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;
          
        TrieNode(){
            isEndOfWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };
       
    static TrieNode root; 
      
    // If not present, inserts key into trie
    // If the key is prefix of trie node, 
    // just marks leaf node
    static void insert(String key)
    {
        int level;
        int length = key.length();
        int index;
       
        TrieNode pCrawl = root;
       
        for (level = 0; level < length; level++)
        {
            index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
       
            pCrawl = pCrawl.children[index];
        }
       
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }
       
    // Returns true if key presents in trie, else false
    static boolean search(String key)
    {
        int level;
        int length = key.length();
        int index;
        TrieNode pCrawl = root;
       
        for (level = 0; level < length; level++)
        {
            index = key.charAt(level) - 'a';
       
            if (pCrawl.children[index] == null)
                return false;
       
            pCrawl = pCrawl.children[index];
        }
       
        return (pCrawl.isEndOfWord);
    }
       
    // Driver
    public static void main(String args[])
    {
        // Input keys (use only 'a' through 'z' and lower case)
        String keys[] = {"the", "a", "there", "answer", "any",
                         "by", "bye", "their"};
       
        String output[] = {"Not present in trie", "Present in trie"};
       
       
        root = new TrieNode();
       
        // Construct trie
        int i;
        for (i = 0; i < keys.length ; i++)
            insert(keys[i]);
       
        // Search for different keys
        if(search("the") == true)
            System.out.println("the --- " + output[1]);
        else System.out.println("the --- " + output[0]);
          
        if(search("these") == true)
            System.out.println("these --- " + output[1]);
        else System.out.println("these --- " + output[0]);
          
        if(search("their") == true)
            System.out.println("their --- " + output[1]);
        else System.out.println("their --- " + output[0]);
          
        if(search("thaw") == true)
            System.out.println("thaw --- " + output[1]);
        else System.out.println("thaw --- " + output[0]);
         
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program for insert and search
# operation in a Trie
  
class TrieNode:
      
    # Trie node class
    def __init__(self):
        self.children = [None]*26
  
        # isEndOfWord is True if node represent the end of the word
        self.isEndOfWord = False
  
class Trie:
      
    # Trie data structure class
    def __init__(self):
        self.root = self.getNode()
  
    def getNode(self):
      
        # Returns new trie node (initialized to NULLs)
        return TrieNode()
  
    def _charToIndex(self,ch):
          
        # private helper function
        # Converts key current character into index
        # use only 'a' through 'z' and lower case
          
        return ord(ch)-ord('a')
  
  
    def insert(self,key):
          
        # If not present, inserts key into trie
        # If the key is prefix of trie node, 
        # just marks leaf node
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
  
            # if current character is not present
            if not pCrawl.children[index]:
                pCrawl.children[index] = self.getNode()
            pCrawl = pCrawl.children[index]
  
        # mark last node as leaf
        pCrawl.isEndOfWord = True
  
    def search(self, key):
          
        # Search key in the trie
        # Returns true if key presents 
        # in trie, else false
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
  
        return pCrawl.isEndOfWord
  
# driver function
def main():
  
    # Input keys (use only 'a' through 'z' and lower case)
    keys = ["the","a","there","anaswe","any",
            "by","their"]
    output = ["Not present in trie",
              "Present in trie"]
  
    # Trie object
    t = Trie()
  
    # Construct trie
    for key in keys:
        t.insert(key)
  
    # Search for different keys
    print("{} ---- {}".format("the",output[t.search("the")]))
    print("{} ---- {}".format("these",output[t.search("these")]))
    print("{} ---- {}".format("their",output[t.search("their")]))
    print("{} ---- {}".format("thaw",output[t.search("thaw")]))
  
if __name__ == '__main__':
    main()
  
# This code is contributed by Atul Kumar (www.facebook.com/atul.kr.007)

C#

// C# implementation of search and 
// insert operations on Trie
using System;
      
public class Trie 
{
      
    // Alphabet size (# of symbols)
    static readonly int ALPHABET_SIZE = 26;
      
    // trie node
    class TrieNode
    {
        public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
      
        // isEndOfWord is true if the node represents
        // end of a word
        public bool isEndOfWord;
          
        public TrieNode()
        {
            isEndOfWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };
      
    static TrieNode root; 
      
    // If not present, inserts key into trie
    // If the key is prefix of trie node, 
    // just marks leaf node
    static void insert(String key)
    {
        int level;
        int length = key.Length;
        int index;
      
        TrieNode pCrawl = root;
      
        for (level = 0; level < length; level++)
        {
            index = key[level] - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
      
            pCrawl = pCrawl.children[index];
        }
      
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }
      
    // Returns true if key 
    // presents in trie, else false
    static bool search(String key)
    {
        int level;
        int length = key.Length;
        int index;
        TrieNode pCrawl = root;
      
        for (level = 0; level < length; level++)
        {
            index = key[level] - 'a';
      
            if (pCrawl.children[index] == null)
                return false;
      
            pCrawl = pCrawl.children[index];
        }
      
        return (pCrawl.isEndOfWord);
    }
      
    // Driver
    public static void Main()
    {
        // Input keys (use only 'a' 
        // through 'z' and lower case)
        String []keys = {"the", "a", "there", "answer", 
                        "any", "by", "bye", "their"};
      
        String []output = {"Not present in trie", "Present in trie"};
      
      
        root = new TrieNode();
      
        // Construct trie
        int i;
        for (i = 0; i < keys.Length ; i++)
            insert(keys[i]);
      
        // Search for different keys
        if(search("the") == true)
            Console.WriteLine("the --- " + output[1]);
        else Console.WriteLine("the --- " + output[0]);
          
        if(search("these") == true)
            Console.WriteLine("these --- " + output[1]);
        else Console.WriteLine("these --- " + output[0]);
          
        if(search("their") == true)
            Console.WriteLine("their --- " + output[1]);
        else Console.WriteLine("their --- " + output[0]);
          
        if(search("thaw") == true)
            Console.WriteLine("thaw --- " + output[1]);
        else Console.WriteLine("thaw --- " + output[0]);
          
    }
}
  
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
// Javascript implementation of search and insert operations
// on Trie
  
// Alphabet size (# of symbols)
let ALPHABET_SIZE = 26;
  
// trie node
class TrieNode
{
    constructor()
    {
        this.isEndOfWord = false;
        this.children = new Array(ALPHABET_SIZE);
        for (let i = 0; i < ALPHABET_SIZE; i++)
            this.children[i] = null;
    }
}
  
let root;
  
// If not present, inserts key into trie
    // If the key is prefix of trie node,
    // just marks leaf node
function insert(key)
{
    let level;
        let length = key.length;
        let index;
        
        let pCrawl = root;
        
        for (level = 0; level < length; level++)
        {
            index = key[level].charCodeAt(0) - 'a'.charCodeAt(0);
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
        
            pCrawl = pCrawl.children[index];
        }
        
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
}
  
// Returns true if key presents in trie, else false
function search(key)
{
    let level;
        let length = key.length;
        let index;
        let pCrawl = root;
        
        for (level = 0; level < length; level++)
        {
            index = key[level].charCodeAt(0) - 'a'.charCodeAt(0);
        
            if (pCrawl.children[index] == null)
                return false;
        
            pCrawl = pCrawl.children[index];
        }
        
        return (pCrawl.isEndOfWord);
}
  
// Driver    
// Input keys (use only 'a' through 'z' and lower case)
let keys = ["the", "a", "there", "answer", "any",
                 "by", "bye", "their"];
  
let output = ["Not present in trie", "Present in trie"];
  
  
root = new TrieNode();
  
// Construct trie
let i;
for (i = 0; i < keys.length ; i++)
    insert(keys[i]);
  
// Search for different keys
if(search("the") == true)
    document.write("the --- " + output[1]+"<br>");
else 
    document.write("the --- " + output[0]+"<br>");
  
if(search("these") == true)
    document.write("these --- " + output[1]+"<br>");
else
    document.write("these --- " + output[0]+"<br>");
  
if(search("their") == true)
    document.write("their --- " + output[1]+"<br>");
else
    document.write("their --- " + output[0]+"<br>");
  
if(search("thaw") == true)
    document.write("thaw --- " + output[1]+"<br>");
else
    document.write("thaw --- " + output[0]+"<br>");
  
  
// This code is contributed by patel2127
</script>

PHP

<?php
# PHP program for insert and search operation in a Trie
# Trie node class
class TrieNode 
{
    public $isEnd = false;
    public $children = [];
}
  
class Trie {
    # Trie data structure class
    public $node = null;
  
    //Initializing trie
    public function __construct() 
    {
        $this->node = new TrieNode();
    }
    
    // Inserts a word into the trie.
  
    public function insert($word) 
    {
        $count = strlen($word);
        $node = $this->node;
        for ($i = 0; $i < $count; $i++) {
            $char = $word[$i];
            if (array_key_exists($char, $node->children)) {
                $node = $node->children[$char];
                continue;
            }
            $node->children[$char] = new TrieNode();
            $node = $node->children[$char];
        }
        $node->isEnd = true;
    }
    
    // Returns if the word is in the trie.
       
    public function search($word): bool
    {
        $count = strlen($word);
        $node = $this->node;
        for ($i = 0; $i < $count; $i++) {
            $char = $word[$i];
            if (!array_key_exists($char, $node->children)) {
                return false;
            }
            $node = $node->children[$char];
        }
  
        return $node->isEnd;
    } 
}
    $keys = array("the","a","there","answer","any","by","their");
  
    # Trie object
    $t = new Trie();
  
    # Constructing trie
    foreach ($keys as $key) {
        $t->insert($key);
    }
    
   # Searching different words
   print ($t->search("the")==1)?("Yes"):("No");
   echo(' ');
   print ($t->search("this")==1)?("Yes"):("No");
   echo(' ');
   print ($t->search("they")==1)?("Yes"):("No");
   echo(' ');
   print ($t->search("thaw")==1)?("Yes"):("No");
  
# This code is contributed by Sajal Aggarwal.
  
  
?>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *