En informática , un árbol ternario es una estructura de datos de árbol en la que cada nodo tiene como máximo tres nodos secundarios , que generalmente se distinguen como "izquierdo", "medio" y "derecho". Los nodos con hijos son nodos principales y los nodos secundarios pueden contener referencias a sus padres. Fuera del árbol, a menudo hay una referencia al nodo "raíz" (el antepasado de todos los nodos), si existe. Se puede llegar a cualquier nodo en la estructura de datos comenzando en 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 .
Definición
- Borde dirigido : el vínculo del padre al hijo.
- Raíz : el nodo sin padres. Hay como máximo un nodo raíz en un árbol enraizado.
- Nodo hoja : cualquier nodo que no tenga hijos.
- Nodo principal : cualquier nodo conectado por un borde dirigido a su hijo o hijos.
- Nodo secundario : cualquier nodo conectado a un nodo principal mediante un borde dirigido.
- Profundidad : longitud de la ruta desde la raíz hasta el nodo. El conjunto de todos los nodos a una profundidad determinada a veces se denomina nivel del árbol. El nodo raíz está en profundidad cero.
- Altura : longitud de la ruta desde la raíz hasta el nodo más profundo del árbol. Un árbol (enraizado) con un solo nodo (la raíz) tiene una altura de cero. En el diagrama de ejemplo, el árbol tiene una altura de 2.
- Hermano : nodos que comparten el mismo nodo principal.
- Un nodo p es un antepasado de un nodo q si existe en la ruta de q a la raíz. El nodo q se denomina entonces descendiente de p.
- El tamaño de un nodo es el número de descendientes que tiene incluyéndose a sí mismo.
Propiedades de los árboles ternarios
- Número máximo de nodos
- Dejar sea la altura de un árbol ternario.
- Dejar ser el número máximo de nodos en un árbol ternario de altura h
h | M ( h ) |
---|---|
0 | 1 |
1 | 4 |
2 | 13 |
3 | 40 |
-
- Cada árbol de altura h tiene como máximo nodos.
- Si un nodo ocupa el árbol , entonces su hijo izquierdo se almacena en TREE.
- Mid Child se almacena en TREE.
- El niño derecho se almacena en el ÁRBOL.
Operaciones comunes
Inserción
Los nodos pueden insertarse en árboles ternarios entre otros tres nodos o agregarse después de un nodo externo . En los árboles ternarios, un nodo que se inserta se especifica en cuanto a qué hijo es.
Nodos externos
Supongamos que el nodo externo que se está agregando 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 el nodo A como padre.
Nodos internos
La inserción en los nodos internos es más compleja que en los 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 de manera similar 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 a su padre como el nuevo nodo.
Supresión
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.
Nodo con cero o un hijo
Digamos que el nodo 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.
Comparación con otros árboles
La siguiente imagen es un árbol de búsqueda binaria que representa 12 palabras de dos letras. Todos los nodos del hijo de la izquierda tienen valores más pequeños, mientras que todos los del hijo de la derecha tienen valores mayores 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 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 de en o para
cada palabra de entrada se muestra debajo del nodo que la representa. En un árbol que representa palabras en 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, uno accede a un elemento de la matriz, prueba si es nulo y toma una rama.
I / | \ / | \ bso / | \ / \ | \ aehntnt | \ | / \ | syefro \ t
La imagen de arriba es un árbol de búsqueda ternario equilibrado para el mismo conjunto de 12 palabras. Los punteros bajo y alto se muestran como líneas en ángulo, mientras que los punteros iguales se muestran como líneas verticales. La búsqueda de la palabra "IS" comienza en la raíz, continúa por el hijo igual hasta el nodo con valor "S" y se detiene allí después de dos comparaciones. Una búsqueda de "AX" hace 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]
Ejemplos de árboles ternarios
- Árbol de búsqueda ternario
- Montón ternario
- Dos árboles ternarios infinitos que contienen todas las triples pitagóricas primitivas se describen en Árbol de las triples pitagóricas primitivas y en Fórmulas para generar triples pitagóricas . El nodo raíz en ambos árboles contiene triple [3, 4, 5]. [2]