En informática , un árbol de búsqueda ternario es un tipo de trie (a veces llamado árbol de prefijos ) donde los nodos se organizan de manera similar a un árbol de búsqueda binario , pero con hasta tres hijos en lugar del límite de dos del árbol binario. Al igual que otros árboles de prefijos, un árbol de búsqueda ternario se puede utilizar como una estructura de mapa asociativo con la capacidad de búsqueda de cadenas incrementales . Sin embargo, los árboles de búsqueda ternarios son más eficientes en cuanto al espacio en comparación con los árboles de prefijos estándar, a costa de la velocidad. Las aplicaciones comunes de los árboles de búsqueda ternarios incluyen la revisión ortográfica y la autocompletación .
Árbol de búsqueda ternario (TST) | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||
|
Descripción
Cada nodo de un árbol de búsqueda ternario almacena un solo carácter , un objeto (o un puntero a un objeto dependiendo de la implementación), y apunta a sus tres hijos convencionalmente denominados igual niño , lo niño y hi niño , que también se pueden referir respectivamente como medio (niño) , inferior (niño) y superior (niño) . [1] Un nodo también puede tener un puntero a su nodo principal, así como un indicador de si el nodo marca o no el final de una palabra. [2] El puntero lo kid debe apuntar a un nodo cuyo valor de carácter sea menor que el nodo actual . El puntero hi kid debe apuntar a un nodo cuyo carácter sea mayor que el nodo actual . [1] El niño igual señala el siguiente carácter de la palabra. La siguiente figura muestra un árbol de búsqueda ternario con las cadenas "cute", "cup", "at", "as", "he", "us" e "i":
C / | \ auh | | | \ tteu / / | / | speis
Al igual que con otras estructuras de datos trie, cada nodo en un árbol de búsqueda ternario representa un prefijo de las cadenas almacenadas. Todas las cadenas del subárbol central de un nodo comienzan con ese prefijo.
Operaciones
Inserción
[ ejemplo necesario ]
La inserción de un valor en una búsqueda ternaria se puede definir de forma recursiva de la misma forma que se definen las búsquedas. Este método recursivo se invoca continuamente en los nodos del árbol a los que se les da una clave que se acorta progresivamente al podar los caracteres del frente de la clave. Si este método llega a un nodo que no ha sido creado, crea el nodo y le asigna el valor de carácter del primer carácter de la clave. Ya sea que se cree o no un nuevo nodo, el método verifica si el primer carácter de la cadena es mayor o menor que el valor del carácter en el nodo y realiza una llamada recursiva en el nodo apropiado como en la operación de búsqueda. Sin embargo, si el primer carácter de la clave es igual al valor del nodo, se invoca el procedimiento de inserción en el niño igual y se elimina el primer carácter de la clave. [1] Al igual que los árboles de búsqueda binaria y otras estructuras de datos , los árboles de búsqueda ternarios pueden volverse degenerados según el orden de las claves. [3] [ fuente autoeditada? ] Insertar claves en orden alfabético es una forma de lograr el peor árbol degenerado posible. [1] Insertar las claves en orden aleatorio a menudo produce un árbol bien equilibrado. [1]
Buscar
[ ejemplo necesario ]
Para buscar un nodo en particular o los datos asociados con un nodo, se necesita una clave de cadena. Un procedimiento de búsqueda comienza verificando el nodo raíz del árbol y determinando cuál de las siguientes condiciones ha ocurrido. Si el primer carácter de la cadena es menor que el carácter en el nodo raíz, se puede llamar a una búsqueda recursiva en el árbol cuya raíz es la raíz inferior de la raíz actual. De manera similar, si el primer carácter es mayor que el nodo actual en el árbol, entonces se puede realizar una llamada recursiva al árbol cuya raíz es el hi-kid del nodo actual. [1] Como último caso, si el primer carácter de la cadena es igual al carácter del nodo actual, la función devuelve el nodo si no hay más caracteres en la clave. Si hay más caracteres en la clave, entonces se debe eliminar el primer carácter de la clave y se realiza una llamada recursiva dado el nodo de niño igual y la clave modificada. [1] Esto también se puede escribir de forma no recursiva utilizando un puntero al nodo actual y un puntero al carácter actual de la clave. [1]
Pseudocódigo
función de búsqueda ( consulta de cadena ) es si is_empty ( consulta ) luego devuelve falso nodo p : = raíz int idx : = 0 mientras que p no es nulo hacer si consulta [ idx ] < p .splitchar entonces p : = p .izquierda else si consulta [ idx ]> p .splitchar entonces p : = p .derecha; de lo contrario, si idx = last_valid_index ( consulta ) , devuelve verdadero idx : = idx + 1 p : = p .center devolver falso
Supresión
[ aclaración necesaria ] [ ejemplo necesario ]
El recorrido
[ aclaración necesaria ] [ ejemplo necesario ]
Búsqueda de coincidencia parcial
[ aclaración necesaria ] [ ejemplo necesario ]
Búsqueda de vecinos cercanos
[ aclaración necesaria ] [ ejemplo necesario ]
Tiempo de ejecución
El tiempo de ejecución de los árboles de búsqueda ternarios varía significativamente con la entrada. Los árboles de búsqueda ternarios funcionan mejor cuando se les dan varias cadenas similares , especialmente cuando esas cadenas comparten un prefijo común . Alternativamente, los árboles de búsqueda ternarios son efectivos cuando se almacenan una gran cantidad de cadenas relativamente cortas (como palabras en un diccionario ). [1] Los tiempos de ejecución de los árboles de búsqueda ternarios son similares a los de los árboles de búsqueda binarios , ya que normalmente se ejecutan en tiempo logarítmico, pero pueden ejecutarse en tiempo lineal en el caso degenerado (el peor).
Complejidades de tiempo para operaciones de árbol de búsqueda ternaria: [1]
Tiempo promedio de ejecución del caso | Tiempo de ejecución en el peor de los casos | |
---|---|---|
Buscar | O (log n ) | O ( n ) |
Inserción | O (log n ) | O ( n ) |
Borrar | O (log n ) | O ( n ) |
Comparación con otras estructuras de datos
Intentos
Si bien son más lentos que otros árboles de prefijos , los árboles de búsqueda ternarios pueden ser más adecuados para conjuntos de datos más grandes debido a su eficiencia espacial. [1]
Mapas hash
Las tablas hash también se pueden usar en lugar de árboles de búsqueda ternarios para mapear cadenas a valores. Sin embargo, los mapas hash también utilizan con frecuencia más memoria que los árboles de búsqueda ternarios (pero no tanto como los intentos). Además, los mapas hash suelen ser más lentos al informar una cadena que no está en la misma estructura de datos, porque debe comparar toda la cadena en lugar de solo los primeros caracteres. Existe alguna evidencia que muestra que los árboles de búsqueda ternarios se ejecutan más rápido que los mapas hash. [1] Además, los mapas hash no permiten muchos de los usos de los árboles de búsqueda ternarios, como las búsquedas de vecinos cercanos .
DAFSA ( autómata de estado finito acíclico determinista )
Si el almacenamiento de palabras del diccionario es todo lo que se requiere (es decir, no se requiere el almacenamiento de información auxiliar para cada palabra), un autómata de estado finito acíclico determinista mínimo (DAFSA) usaría menos espacio que un árbol de búsqueda trie o ternario. Esto se debe a que un DAFSA puede comprimir ramas idénticas del trie que corresponden a los mismos sufijos (o partes) de diferentes palabras que se almacenan.
Usos
Los árboles de búsqueda ternaria se pueden utilizar para resolver muchos problemas en los que se debe almacenar y recuperar una gran cantidad de cadenas en un orden arbitrario. Algunos de los más comunes o útiles se encuentran a continuación:
- Siempre que se pueda utilizar un trie , se prefiere una estructura que consuma menos memoria. [1]
- Una estructura de datos rápida y que ahorra espacio para mapear cadenas a otros datos. [3]
- Para implementar la finalización automática . [2] [ fuente autoeditada? ]
- Como corrector ortográfico . [4]
- Búsqueda de vecinos cercanos (de los cuales la revisión ortográfica es un caso especial). [1]
- Como base de datos , es deseable especialmente cuando se indexa por varios campos no clave. [4]
- En lugar de una tabla hash . [4]
Ver también
Referencias
- ^ a b c d e f g h i j k l m n "Árboles de búsqueda ternarios" . Dr. Dobb's .
- ^ a b Ostrovsky, Igor. "Autocompletar eficiente con un árbol de búsqueda ternario" .
- ^ a b Wrobel, Lukasz. "Árbol de búsqueda ternaria" .
- ^ a b c Flint, Wally (16 de febrero de 2001). "Plante sus datos en un árbol de búsqueda ternario" . JavaWorld . Consultado el 19 de julio de 2020 .
enlaces externos
- Página de árboles de búsqueda ternaria con artículos (por Jon Bentley y Robert Sedgewick) sobre árboles de búsqueda ternaria y algoritmos para "ordenar y buscar cadenas"
- Intentos de búsqueda ternaria : un vídeo de Robert Sedgewick
- TST.java.html Implementación en Java de un TST por Robert Sedgewick y Kevin Wayne