En informática , un árbol de búsqueda ternario es un tipo de trie (a veces llamado árbol de prefijos ) donde los nodos están dispuestos 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 para los árboles de búsqueda ternarios incluyen la corrección ortográfica y el autocompletado .
Cada nodo de un árbol de búsqueda ternario almacena un único carácter , un objeto (o un puntero a un objeto, dependiendo de la implementación) y punteros a sus tres hijos, denominados convencionalmente equal kid , lo kid y hi kid , que también pueden denominarse respectivamente middle (child) , lower (child) y higher (child) . [1] Un nodo también puede tener un puntero a su nodo padre, 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 valor de carácter sea mayor que el nodo actual . [1] El equal kid apunta al 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":
do / | \ Sí | | | \ teu / / | / | speis
Al igual que con otras estructuras de datos trie, cada nodo de 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.
La inserción de un valor en una búsqueda ternaria se puede definir de forma recursiva o iterativa, de forma muy similar a como se definen las búsquedas. Este método recursivo se llama continuamente en los nodos del árbol que tienen una clave que se acorta progresivamente al eliminar caracteres del frente de la clave. Si este método llega a un nodo que no se ha creado, crea el nodo y le asigna el valor del carácter del primer carácter de la clave. Ya sea que se cree un nuevo nodo o no, el método verifica si el primer carácter de la cadena es mayor o menor que el valor del carácter del 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, entonces se llama al 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 binarios y otras estructuras de datos , los árboles de búsqueda ternarios pueden degenerarse dependiendo del orden de las claves. [3] [ fuente autopublicada? ] 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]
función inserción ( cadena clave ) es nodo p := raíz //inicializado para ser igual en caso de que raíz sea nulo nodo último := raíz int idx := 0 mientras p no sea nulo hacer //recurrir en el subárbol apropiado si clave [ idx ] < p . splitchar entonces último := p p := p . left de lo contrario si clave [ idx ] > p . splitchar entonces último := p p := p . right de lo contrario : // la clave ya está en nuestro árbol si idx == longitud ( clave ) entonces retorna //recorta el carácter de nuestra clave idx := idx + 1 último := p p := p . mid p := nodo () //agrega p como un hijo del último nodo no nulo (o raíz si raíz es nulo) si raíz == nulo entonces raíz := p de lo contrario si último . splitchar < clave [ idx ] entonces último . right := p de lo contrario si último . splitchar > clave [ idx ] entonces last . left := p de lo contrario last . mid := p p . splitchar := clave [ idx ] idx := idx + 1 // Insertar resto de clave mientras idx < length ( clave ) hacer p . mid := nodo () p . mid . splitchar := clave [ idx ] idx += 1 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 el hijo lo 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 hacer una llamada recursiva al árbol cuya raíz es el hijo hi del nodo actual. [1] Como caso final, si el primer carácter de la cadena es igual al carácter del nodo actual, entonces 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 hijo igual y la clave modificada. [1] Esto también se puede escribir de manera no recursiva usando un puntero al nodo actual y un puntero al carácter actual de la clave. [1]
función buscar ( consulta de cadena ) es si está_vacío ( consulta ) entonces devuelve falso nodo p := raíz int idx := 0 mientras p no sea nulo hacer si consulta [ idx ] < p . splitchar entonces p := p . left de lo contrario si consulta [ idx ] > p . splitchar entonces p := p . right ; de lo contrario si idx = length ( consulta ) entonces devuelve verdadero idx := idx + 1 p := p . mid devuelve falso La operación de eliminación consiste en buscar una cadena clave en el árbol de búsqueda y encontrar un nodo, llamado firstMid en el pseudocódigo siguiente, de modo que la ruta desde el hijo intermedio de firstMid hasta el final de la ruta de búsqueda de la cadena clave no tenga hijos izquierdos o derechos. Esto representaría un sufijo único en el árbol ternario correspondiente a la cadena clave. Si no existe dicha ruta, significa que la cadena clave está completamente contenida como prefijo de otra cadena o no está en el árbol de búsqueda. Muchas implementaciones utilizan un carácter de fin de cadena para garantizar que solo se produzca el último caso. A continuación, se elimina la ruta desde firstMid.mid hasta el final de la ruta de búsqueda. En el caso de que firstMid sea la raíz, la cadena clave debe haber sido la última cadena del árbol y, por lo tanto, la raíz se establece en nula después de la eliminación.
función eliminar ( cadena clave ) es si está_vacío ( clave ) entonces devuelve nodo p := raíz int idx := 0 nodo firstMid := null mientras p no sea null hacer si clave [ idx ] < p . splitchar entonces firstMid := null p := p . left de lo contrario si clave [ idx ] > p . splitchar entonces firstMid := null p := p . right de lo contrario firstMid := p mientras p no sea null y clave [ idx ] == p . splitchar hacer idx := idx + 1 p := p . mid si firstMid == null entonces devolver // Sin sufijo de cadena único // En este punto, firstMid apunta al nodo antes de que aparezca el sufijo único de la cadena node q := firstMid . mid node p := q firstMid . mid := null // desconecta el sufijo del árbol mientras q no sea nulo do // recorre la ruta del sufijo y elimina los nodos p := q q := q . mid delete ( p ) // libera memoria asociada con el nodo p if firstMid == root then delete ( root ) // elimina todo el árbol root := null [ aclaración necesaria ] [ ejemplo necesario ]
[ aclaración necesaria ] [ ejemplo necesario ]
[ aclaración necesaria ] [ ejemplo necesario ]
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 dan varias cadenas similares , especialmente cuando esas cadenas comparten un prefijo común . Alternativamente, los árboles de búsqueda ternarios son efectivos cuando se almacena 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 , en el sentido de que normalmente se ejecutan en tiempo logarítmico, pero pueden ejecutarse en tiempo lineal en el caso degenerado (el peor). Además, también se debe tener en cuenta el tamaño de las cadenas al considerar el tiempo de ejecución. Por ejemplo, en la ruta de búsqueda de una cadena de longitud k , habrá k recorridos hacia abajo de los hijos del medio en el árbol, así como un número logarítmico de recorridos hacia abajo de los hijos izquierdo y derecho en el árbol. Por lo tanto, en un árbol de búsqueda ternario en una pequeña cantidad de cadenas muy grandes, las longitudes de las cadenas pueden dominar el tiempo de ejecución. [4]
Complejidades temporales para operaciones de árboles de búsqueda ternarios: [1]
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]
Las tablas hash también se pueden utilizar en lugar de árboles de búsqueda ternarios para mapear cadenas a valores. Sin embargo, los mapas hash también usan con frecuencia más memoria que los árboles de búsqueda ternarios (pero no tanto como tries). Además, los mapas hash son típicamente más lentos al informar una cadena que no está en la misma estructura de datos, porque deben comparar la cadena completa en lugar de solo los primeros caracteres. Hay 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 .
Si lo único que se requiere es almacenar palabras del diccionario (es decir, no se requiere almacenar información auxiliar para cada palabra), un autómata de estado finito acíclico determinista mínimo (DAFSA) utilizaría menos espacio que un trie o un árbol de búsqueda 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.
Los árboles de búsqueda ternarios 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 son los siguientes: