Un árbol de búsqueda ternario es una estructura de datos trie especial donde los Nodes secundarios de un trie estándar se ordenan como un árbol de búsqueda binario.
Representación de árboles de búsqueda ternarios: a
diferencia de la estructura de datos trie (estándar) donde cada Node contiene 26 punteros para sus hijos, cada Node en un árbol de búsqueda ternario contiene solo 3 punteros:
1. El puntero izquierdo apunta al Node cuyo valor es menor que el valor en el Node actual.
2. El puntero igual apunta al Node cuyo valor es igual al valor en el Node actual.
3. El puntero derecho apunta al Node cuyo valor es mayor que el valor del Node actual.
Además de los tres punteros anteriores, cada Node tiene un campo para indicar datos (carácter en el caso de un diccionario) y otro campo para marcar el final de una string.
Entonces, más o menos es similar a BST, que almacena datos en función de algún orden. Sin embargo, los datos en un árbol de búsqueda ternario se distribuyen entre los Nodes. por ejemplo, necesita 4 Nodes para almacenar la palabra «Geek».
La siguiente figura muestra cómo se almacenan exactamente las palabras en un árbol de búsqueda ternario.
Una de las ventajas de usar árboles de búsqueda ternarios sobre los intentos es que los árboles de búsqueda ternarios son más eficientes en el espacio (involucran solo tres punteros por Node en comparación con 26 en los intentos estándar). Además, los árboles de búsqueda ternarios se pueden usar en cualquier momento en que se use una tabla hash para almacenar strings.
Los intentos son adecuados cuando hay una distribución adecuada de palabras en los alfabetos para que los espacios se utilicen de manera más eficiente. De lo contrario, los árboles de búsqueda ternarios son mejores. Los árboles de búsqueda ternarios son eficientes de usar (en términos de espacio) cuando las strings que se almacenarán comparten un prefijo común.
Aplicaciones de los árboles de búsqueda ternarios:
1. Los árboles de búsqueda ternarios son eficientes para consultas como «Dada una palabra, encuentre la siguiente palabra en el diccionario (búsquedas de vecinos cercanos)» o «Encuentre todos los números de teléfono que comiencen con 9342 o «escriba algunos caracteres iniciales en un navegador web muestra todos los nombres de sitios web con este prefijo «(función de autocompletar)».
2. Utilizado en correctores ortográficos: los árboles de búsqueda ternarios se pueden utilizar como diccionario para almacenar todas las palabras. Una vez que la palabra se escribe en un editor, la palabra se puede buscar de forma paralela en el árbol de búsqueda ternario para comprobar que la ortografía sea correcta.
Implementación:
A continuación se muestra la implementación en C del árbol de búsqueda ternario. Las operaciones implementadas son búsqueda, inserción y recorrido.
C++
// C++ program to demonstrate Ternary Search Tree (TST)
// insert, traverse and search operations
#include <bits/stdc++.h>
using namespace std;
#define MAX 50
// A node of ternary search tree
struct Node {
char data;
// True if this character is last character of one of
// the words
unsigned isEndOfString = 1;
Node *left, *eq, *right;
};
// A utility function to create a new ternary search tree
// node
Node* newNode(char data)
{
Node* temp = new Node();
temp->data = data;
temp->isEndOfString = 0;
temp->left = temp->eq = temp->right = NULL;
return temp;
}
// Function to insert a new word in a Ternary Search Tree
void insert(Node** root, char* word)
{
// Base Case: Tree is empty
if (!(*root))
*root = newNode(*word);
// If current character of word is smaller than root's
// character, then insert this word in left subtree of
// root
if ((*word) < (*root)->data)
insert(&((*root)->left), word);
// If current character of word is greater than root's
// character, then insert this word in right subtree of
// root
else if ((*word) > (*root)->data)
insert(&((*root)->right), word);
// If current character of word is same as root's
// character,
else {
if (*(word + 1))
insert(&((*root)->eq), word + 1);
// the last character of the word
else
(*root)->isEndOfString = 1;
}
}
// A recursive function to traverse Ternary Search Tree
void traverseTSTUtil(Node* root, char* buffer, int depth)
{
if (root) {
// First traverse the left subtree
traverseTSTUtil(root->left, buffer, depth);
// Store the character of this node
buffer[depth] = root->data;
if (root->isEndOfString) {
buffer[depth + 1] = '\0';
cout << buffer << endl;
}
// Traverse the subtree using equal pointer (middle
// subtree)
traverseTSTUtil(root->eq, buffer, depth + 1);
// Finally Traverse the right subtree
traverseTSTUtil(root->right, buffer, depth);
}
}
// The main function to traverse a Ternary Search Tree.
// It mainly uses traverseTSTUtil()
void traverseTST(struct Node* root)
{
char buffer[MAX];
traverseTSTUtil(root, buffer, 0);
}
// Function to search a given word in TST
int searchTST(Node* root, char* word)
{
if (!root)
return 0;
if (*word < (root)->data)
return searchTST(root->left, word);
else if (*word > (root)->data)
return searchTST(root->right, word);
else {
if (*(word + 1) == '\0')
return root->isEndOfString;
return searchTST(root->eq, word + 1);
}
}
// Driver program to test above functions
int main()
{
Node* root = NULL;
char cat[] = "cat";
char cats[] = "cats";
char up[] = "up";
char bug[] = "bug";
char bu[] = "bu";
insert(&root, cat);
insert(&root, cats);
insert(&root, up);
insert(&root, bug);
cout << "Following is traversal of ternary search "
"tree\n";
traverseTST(root);
cout << "\nFollowing are search results for cats, bu "
"and cat respectively\n";
searchTST(root, cats) ? cout << "Found\n"
: cout << "Not Found\n";
searchTST(root, bu) ? cout << "Found\n"
: cout << "Not Found\n";
searchTST(root, cat) ? cout << "Found\n"
: cout << "Not Found\n";
return 0;
}
// This code is contributed by tapeshdua420.
C
// C program to demonstrate Ternary Search Tree (TST) insert, traverse
// and search operations
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
// A node of ternary search tree
struct Node
{
char data;
// True if this character is last character of one of the words
unsigned isEndOfString: 1;
struct Node *left, *eq, *right;
};
// A utility function to create a new ternary search tree node
struct Node* newNode(char data)
{
struct Node* temp = (struct Node*) malloc(sizeof( struct Node ));
temp->data = data;
temp->isEndOfString = 0;
temp->left = temp->eq = temp->right = NULL;
return temp;
}
// Function to insert a new word in a Ternary Search Tree
void insert(struct Node** root, char *word)
{
// Base Case: Tree is empty
if (!(*root))
*root = newNode(*word);
// If current character of word is smaller than root's character,
// then insert this word in left subtree of root
if ((*word) < (*root)->data)
insert(&( (*root)->left ), word);
// If current character of word is greater than root's character,
// then insert this word in right subtree of root
else if ((*word) > (*root)->data)
insert(&( (*root)->right ), word);
// If current character of word is same as root's character,
else
{
if (*(word+1))
insert(&( (*root)->eq ), word+1);
// the last character of the word
else
(*root)->isEndOfString = 1;
}
}
// A recursive function to traverse Ternary Search Tree
void traverseTSTUtil(struct Node* root, char* buffer, int depth)
{
if (root)
{
// First traverse the left subtree
traverseTSTUtil(root->left, buffer, depth);
// Store the character of this node
buffer[depth] = root->data;
if (root->isEndOfString)
{
buffer[depth+1] = '\0';
printf( "%s\n", buffer);
}
// Traverse the subtree using equal pointer (middle subtree)
traverseTSTUtil(root->eq, buffer, depth + 1);
// Finally Traverse the right subtree
traverseTSTUtil(root->right, buffer, depth);
}
}
// The main function to traverse a Ternary Search Tree.
// It mainly uses traverseTSTUtil()
void traverseTST(struct Node* root)
{
char buffer[MAX];
traverseTSTUtil(root, buffer, 0);
}
// Function to search a given word in TST
int searchTST(struct Node *root, char *word)
{
if (!root)
return 0;
if (*word < (root)->data)
return searchTST(root->left, word);
else if (*word > (root)->data)
return searchTST(root->right, word);
else
{
if (*(word+1) == '\0')
return root->isEndOfString;
return searchTST(root->eq, word+1);
}
}
// Driver program to test above functions
int main()
{
struct Node *root = NULL;
insert(&root, "cat");
insert(&root, "cats");
insert(&root, "up");
insert(&root, "bug");
printf("Following is traversal of ternary search tree\n");
traverseTST(root);
printf("\nFollowing are search results for cats, bu and cat respectively\n");
searchTST(root, "cats")? printf("Found\n"): printf("Not Found\n");
searchTST(root, "bu")? printf("Found\n"): printf("Not Found\n");
searchTST(root, "cat")? printf("Found\n"): printf("Not Found\n");
return 0;
}
Producción:
Following is traversal of ternary search tree bug cat cats up Following are search results for cats, bu and cat respectively Found Not Found Found
Complejidad de tiempo: La complejidad de tiempo de las operaciones del árbol de búsqueda ternario es similar a la del árbol de búsqueda binario. es decir, las operaciones de inserción, borrado y búsqueda toman un tiempo proporcional a la altura del árbol de búsqueda ternario. El espacio es proporcional a la longitud de la string a almacenar.
Referencia:
http://en.wikipedia.org/wiki/Ternary_search_tree
Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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