Árbol binario roscado - Threaded binary tree

Un árbol enhebrado , con los enlaces de enhebrado especiales mostrados por flechas discontinuas

En informática , un árbol binario enhebrado es una variante de árbol binario que facilita el recorrido en un orden particular (a menudo el mismo orden ya definido para el árbol).

Se puede recorrer fácilmente un árbol de búsqueda binario completo en el orden de la clave principal, pero con solo un puntero a un nodo, encontrar el siguiente nodo puede ser lento o imposible. Por ejemplo, los nodos hoja, por definición, no tienen descendientes, por lo que no se puede llegar a ningún otro nodo con solo un puntero a un nodo hoja, por supuesto que incluye el nodo "siguiente" deseado. Un árbol enhebrado agrega información adicional en algunos o todos los nodos, por lo que el nodo "siguiente" se puede encontrar rápidamente. También se puede atravesar sin recursividad y el almacenamiento extra (proporcional a la profundidad del árbol) que requiere.

Enhebrar

"Un árbol binario se enhebra haciendo que todos los punteros secundarios correctos que normalmente serían nulos apunten al sucesor en orden del nodo ( si existe), y todos los punteros secundarios izquierdos que normalmente serían nulos apunten al predecesor en orden del nodo ".

Esto supone que el orden de recorrido es el mismo que el recorrido en orden del árbol. Sin embargo, los punteros se pueden agregar (o además) a los nodos del árbol, en lugar de reemplazarlos. Las listas enlazadas así definidas también se denominan comúnmente "subprocesos" y se pueden utilizar para permitir el recorrido en cualquier orden deseado. Por ejemplo, un árbol cuyos nodos representan información sobre personas puede ordenarse por nombre, pero tiene subprocesos adicionales que permiten un recorrido rápido por orden de fecha de nacimiento, peso o cualquier otra característica conocida.

Motivación

Los árboles, incluidos (pero no limitados a) árboles de búsqueda binarios , se pueden usar para almacenar elementos en un orden particular, como el valor de alguna propiedad almacenada en cada nodo, a menudo llamada clave . Una operación útil en un árbol de este tipo es el recorrido : visitar todos los elementos en el orden de la clave.

Un algoritmo de recorrido recursivo simple que visita cada nodo de un árbol de búsqueda binaria es el siguiente. Suponga que t es un puntero a un nodo, o nil . "Visitar" t puede significar realizar cualquier acción sobre el nodo t o su contenido.

Un problema con este algoritmo es que, debido a su recursividad, utiliza un espacio de pila proporcional a la altura de un árbol. Si el árbol está bastante equilibrado, esto equivale a O (log n ) de espacio para un árbol que contiene n elementos. En el peor de los casos, cuando el árbol toma la forma de una cadena , la altura del árbol es n, por lo que el algoritmo ocupa O ( n ) espacio. Un segundo problema es que todos los recorridos deben comenzar en la raíz cuando los nodos tienen punteros solo para sus hijos. Es común tener un puntero a un nodo en particular, pero eso no es suficiente para volver al resto del árbol a menos que se agregue información adicional, como punteros de hilo.

En este enfoque, es posible que no sea posible saber si los punteros izquierdo y / o derecho en un nodo dado realmente apuntan a los niños, o son una consecuencia del subproceso. Si la distinción es necesaria, agregar un solo bit a cada nodo es suficiente para registrarlo.

En un libro de texto de 1968, Donald Knuth preguntó si existe un algoritmo no recursivo para el recorrido en orden, que no usa pila y deja el árbol sin modificar. Una de las soluciones a este problema es el enhebrado de árboles, presentado por Joseph M. Morris en 1979. En la edición de seguimiento de 1969, Knuth atribuyó la representación del árbol enhebrado a Perlis y Thornton (1960).

Relación con los indicadores de los padres

Otra forma de lograr objetivos similares es incluir un puntero en cada nodo, al nodo padre de ese nodo. Dado eso, siempre se puede llegar al nodo "siguiente". Los punteros "correctos" siguen siendo nulos siempre que no haya hijos correctos. Para encontrar el nodo "siguiente" de un nodo cuyo puntero derecho es nulo, recorra los punteros "principales" hasta llegar a un nodo cuyo puntero derecho no sea nulo y que no sea el hijo del que acaba de salir. Ese nodo es el "siguiente" nodo, y después vienen sus descendientes a la derecha.

También es posible descubrir el padre de un nodo a partir de un árbol binario enhebrado, sin el uso explícito de punteros padre o una pila, aunque es más lento. Para ver esto, considere un nodo k con el hijo derecho r . Entonces, el puntero izquierdo de r debe ser un hijo o un hilo de regreso a k . En el caso de que r tenga un hijo izquierdo, ese hijo izquierdo debe, a su vez, tener un hijo izquierdo propio o un hilo de regreso a k , y así sucesivamente para todos los hijos izquierdos sucesivos. Entonces, siguiendo la cadena de punteros izquierdos desde r , eventualmente encontraremos un hilo apuntando hacia k . La situación es simétricamente similar cuando q es el hijo izquierdo de p; podemos seguir a los hijos derechos de q hasta un hilo que apunta hacia adelante ap .

Tipos

1. Único subproceso: cada nodo está roscado hacia o bien el antecesor en orden o sucesor (izquierda o derecha).
2. Doble rosca: cada nodo está roscado hacia tanto el predecesor en orden y sucesor (izquierda y derecha).

En Python :

def parent(node):
    if node is node.tree.root:
        return None
    else:
        x = node
        y = node
        while True:
            if is_thread(y):
                p = y.right
                if p is None or p.left is not node:
                    p = x
                    while not is_thread(p.left):
                        p = p.left
                    p = p.left
                return p
            elif is_thread(x):
                p = x.left
                if p is None or p.right is not node:
                    p = y
                    while not is_thread(p.right):
                        p = p.right
                    p = p.right
                return p
            x = x.left
            y = y.right

La matriz de recorrido en orden

Los subprocesos son referencia a los predecesores y sucesores del nodo según un recorrido en orden.

El recorrido en orden del árbol enhebrado es A,B,C,D,E,F,G,H,I, el predecesor de Ees D, el sucesor de Ees F.

Ejemplo

Hagamos el árbol binario enhebrado a partir de un árbol binario normal:

El recorrido en orden para el árbol anterior es - DBAE C. Por lo tanto, el árbol binario subproceso respectivo será -

Enlaces nulos

En un árbol binario de m-way con n nodos, hay n * m - (n-1) enlaces vacíos.

Recorrido iterativo

Existe un algoritmo para atravesar un árbol binario enhebrado sin utilizar la recursividad. En su lugar, cualquier método de este tipo debe utilizar la iteración; es decir, todos los pasos deben realizarse en un bucle para poder visitar todos los nodos del árbol.

El recorrido en orden, por definición, visita primero el subárbol izquierdo de cada nodo (si existe y si aún no se ha visitado); luego visita el nodo mismo, y finalmente el subárbol derecho del nodo (si existe). Si el subárbol derecho no existe, pero hay un enlace enhebrado, hacemos que el nodo enhebrado sea el nodo actual en consideración. A continuación se muestra un ejemplo.

Algoritmo

1. Si el nodo actual tiene un hijo izquierdo que no está en la lista de visitas, vaya al paso 2, de lo contrario al paso 3.
2. Coloque ese hijo izquierdo en la lista de nodos visitados y conviértalo en el nodo actual. Vaya al paso 6.
3. Visita el nodo. Si el nodo tiene un hijo correcto, vaya al paso 4, de lo contrario, vaya al paso 5.
4. Convierta al niño correcto en el nodo actual. Vaya al paso 6.
5. Si hay un nodo de subproceso, conviértalo en el nodo actual.
6. Si se han impreso todos los nodos, finalice, de lo contrario, vaya al paso 1.

Referencias

enlaces externos

• GNU libavl 2.0.2, sección sobre árboles de búsqueda binarios enhebrados