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