En informática , un árbol ternario es una estructura de datos en forma de árbol en la que cada nodo tiene como máximo tres nodos secundarios , que normalmente se distinguen como "izquierdo", "medio" y "derecho". Los nodos con hijos son nodos primarios, y los nodos secundarios pueden contener referencias a sus padres. Fuera del árbol, suele haber una referencia al nodo "raíz" (el antecesor de todos los nodos), si existe. Se puede llegar a cualquier nodo de la estructura de datos comenzando por el nodo raíz y siguiendo repetidamente las referencias al hijo izquierdo, medio o derecho.
Los árboles ternarios se utilizan para implementar árboles de búsqueda ternarios y montones ternarios .
– Sea la altura de un árbol ternario.
– Sea el número máximo de nodos en un árbol ternario de altura h
–
– Cada árbol de altura h tiene como máximo nodos.
Los nodos se pueden insertar en árboles ternarios entre otros tres nodos o se pueden agregar después de un nodo externo . En los árboles ternarios, se especifica qué nodo se inserta en cada árbol ternario.
Digamos que el nodo externo que se agrega es el nodo A. Para agregar un nuevo nodo después del nodo A, A asigna el nuevo nodo como uno de sus hijos y el nuevo nodo asigna al nodo A como su padre.
La inserción en nodos internos es más compleja que en nodos externos. Digamos que el nodo interno es el nodo A y que el nodo B es el hijo de A. (Si la inserción es para insertar un hijo derecho, entonces B es el hijo derecho de A, y lo mismo con una inserción de hijo izquierdo o hijo medio). A asigna su hijo al nuevo nodo y el nuevo nodo asigna su padre a A. Luego, el nuevo nodo asigna su hijo a B y B asigna su padre como el nuevo nodo.
La eliminación es el proceso mediante el cual se elimina un nodo del árbol. Solo ciertos nodos de un árbol ternario pueden eliminarse sin ambigüedades.
Digamos que el nodo que se va a eliminar es el nodo A. Si un nodo no tiene hijos ( nodo externo ), la eliminación se logra estableciendo el hijo del padre de A en nulo y el padre de A en nulo. Si tiene un hijo, establezca el padre del hijo de A en el padre de A y establezca el hijo del padre de A en el hijo de A.
La imagen de abajo es un árbol binario de búsqueda que representa 12 palabras de dos letras. Todos los nodos del hijo izquierdo tienen valores más pequeños, mientras que todos los nodos del hijo derecho tienen valores más grandes para todos los nodos. Una búsqueda comienza desde la raíz. Para encontrar la palabra "ON", la comparamos con "IN" y tomamos la rama derecha. Cada comparación podría acceder a cada carácter de ambas palabras.
en / \ ser de / \ / \ como por es o \ \ \ / \ en él se puso a
La búsqueda digital intenta almacenar cadenas carácter por carácter. La siguiente imagen es un árbol que representa el mismo conjunto de 12 palabras;
_ _ _ _ _ _ _ _ _ _ _ _ _ / / / \ \ \ / / / \ \ \ Abhiot / \ / \ | / | \ /|\ | steyenstfnro como en ser por él en es eso de en o a
Cada palabra de entrada se muestra debajo del nodo que la representa. En un árbol que representa palabras de letras minúsculas, cada nodo tiene una ramificación de 26 vías. Las búsquedas son muy rápidas: una búsqueda de "IS" comienza en la raíz, toma la rama "I", luego la rama "S" y termina en el nodo deseado. En cada nodo, se accede a un elemento de la matriz, se comprueba si es nulo y se toma una rama.
i / | \ / | \ bso / | \ / \ | \ Aehntnt | \ | / \ | siefro \ a
La imagen de arriba es un árbol de búsqueda ternario balanceado para el mismo conjunto de 12 palabras. Los punteros altos y bajos se muestran como líneas en ángulo, mientras que los punteros iguales se muestran como líneas verticales. Una búsqueda de la palabra "IS" comienza en la raíz, continúa hacia abajo por el hijo igual hasta el nodo con el valor "S" y se detiene allí después de dos comparaciones. Una búsqueda de "AX" realiza tres comparaciones con la primera letra "A" y dos comparaciones con la segunda letra "X" antes de informar que la palabra no está en el árbol. [1]
![{\estilo de visualización [k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9278f059ccf89ce18a2e393c1301a934faec8d5d)
![{\estilo de visualización [3k-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/668a5165c53f0009c0bc428db148b86f2bdbe247)
![{\estilo de visualización [3k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d1f255a2a37183afca18caf5fcb9d2ae0e4527e)
![{\estilo de visualización [3k+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb3905c7c7cd14de1670506d9f5a3efbc5040f48)