Un árbol binario cosido es una variante de un árbol binario que permite un recorrido rápido: dado un puntero a un nodo en un árbol cosido, uno puede encontrar fácilmente el siguiente (y/o anterior) nodo en orden .
Los árboles binarios, que incluyen (pero no se limitan a) los árboles de búsqueda binarios y sus variantes, se pueden usar para almacenar varios elementos en un orden particular. Por ejemplo, un árbol de búsqueda binaria asume que los elementos de datos están ordenados de alguna manera y conserva ese orden cuando se insertan y eliminan. Una operación útil en un árbol de este tipo es el recorrido , es decir, visitar los elementos del árbol en el orden en que serán recordados (lo que corresponde al orden de los nodos en el caso de un árbol de búsqueda binaria).
El algoritmo de recorrido recursivo simple que visita cada nodo del árbol de búsqueda binaria es el siguiente. Supongamos que t es un puntero a un nodo, o nil . "Visita" t puede significar cualquier operación con este nodo t o el contenido asignado a él.
Algoritmo transversal ( t ):
El problema de este algoritmo es que, debido a la recursividad, el algoritmo utiliza un espacio de pila proporcional a la altura del árbol. Si el árbol está mal balanceado, este valor llega a O (log n ) para un árbol de 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 requerirá O ( n ) espacio de pila .
En 1968, Donald Knuth preguntó si había un algoritmo de recorrido centrado no recursivo que no usara la pila y dejara el árbol sin cambios. Una solución a este problema es la costura de árboles, introducida por James H. Morris en 1979 [1] [2] .
Un árbol cosido se define de la siguiente manera:
“Un árbol binario se une asignando todos los punteros secundarios derechos, que normalmente serían punteros nulos, a los punteros al siguiente nodo del nodo ( si lo hay), y todos los punteros secundarios izquierdos, que normalmente serían punteros nulos, a los punteros a los nodos anteriores. en el pedido" [3] .
También es posible encontrar el padre de un nodo de un árbol binario cosido sin usar explícitamente un puntero al padre o la pila, aunque es más lento. Esto es útil cuando la pila está restringida, o cuando una pila de punteros principales no está disponible (para encontrar un puntero principal mediante la búsqueda primero en profundidad ).
Para ver cómo esto es posible, considere un nodo k que tiene un hijo derecho r . Entonces el puntero izquierdo del nodo r debe ser un hijo o un puntero de vuelta a k . En el caso de que r tenga un hijo izquierdo, entonces el hijo izquierdo debe tener su propio hijo izquierdo, o un puntero de regreso a k , y así sucesivamente para todos los hijos izquierdos subsiguientes. Por lo tanto, recorriendo la cadena de punteros izquierdos desde r uno tras otro , eventualmente encontramos el puntero de puntada de regreso a k . La situación es simétrica cuando q es el hijo izquierdo de p , en cuyo caso podemos rastrear los hijos derechos del nodo q para obtener un puntero de firmware a p .
En lenguaje Python :
def padre ( nodo ): si nodo es nodo . árbol _ root : devuelve Ninguno más : x = nodo y = nodo while True : if is_thread ( y ): p = y . correcto si p es Ninguno o p . la izquierda no es nodo : p = x mientras que no es_hilo ( p . izquierda ): p = p . izquierda pag = pag . izquierda volver p elif is_thread ( x ): p = x . izquierda si p es Ninguno o p . right no es nodo : p = y while not is_thread ( p . right ): p = p . derecho pag = pag . retorno derecho p x = x . izquierda y = y . CorrectoEl firmware es un enlace a los nodos anterior y siguiente de un nodo dado de acuerdo con un recorrido centrado.
Si el orden del árbol cosido es ABCDEFGHI, el nodo D viene antes que el E y el F sigue al nodo E.
Intentemos formar un árbol cosido a partir de un árbol binario normal.
El orden de vértice transversal centrado para el árbol de arriba es DBAE C. Entonces, el árbol binario cosido correspondiente se vería así
En un árbol binario cosido en m con n nodos, hay n*m - (n-1) enlaces nulos.
Como método de recorrido no recursivo, el método debe ser un procedimiento iterativo, todos los pasos de recorrido de nodo deben estar en un bucle, por lo que se puede aplicar lo mismo a todos los nodos del árbol. Nuevamente asumimos un recorrido de árbol centrado. Luego, para cualquier nodo, atravesamos primero el subárbol izquierdo (si existe y si no lo hemos atravesado antes). Luego visitamos (es decir, imprimimos el valor de los nodos en nuestro caso) el nodo en sí, y solo luego recorremos el subárbol derecho (si existe). Si no hay un árbol correcto, verifique el enlace cosido y haga que el vértice cosido sea el nodo actual en consideración. Vea el ejemplo a continuación.
Paso 1: para el nodo actual, verifique si hay un hijo izquierdo que no está en la lista visitada. Si hay uno, vaya al paso 2, de lo contrario, vaya al paso 3.
Paso 2: coloque el elemento secundario izquierdo en la lista de nodos visitados y conviértalo en el nodo actual. Vayamos al paso 6.
Paso 3: Imprima el nodo y, si el nodo tiene un hijo derecho, vaya al paso 4, de lo contrario, vaya al paso 5.
Paso 4: haga que el hijo correcto sea el nodo actual.
Paso 5: si existe un nodo de firmware, conviértalo en el nodo actual.
Paso 6: si se imprimen todos los nodos, salga; de lo contrario, vaya al paso 1.
| Lista | ||||
|---|---|---|---|---|
| paso 1 | A tiene un hijo izquierdo, es decir, B que aún no ha sido visitado, por lo que colocamos a B en nuestra "lista de nodos visitados" y B se convierte en el nodo actual. | B | ||
| paso 2 | B también tiene un hijo izquierdo D , que no está en la lista de nodos visitados. Ponemos D en la lista de visitas y lo actualizamos. | BD | ||
| paso 3 | El nodo D no tiene un hijo izquierdo, por lo que imprimimos D y luego verificamos el hijo derecho. D no tiene un hijo correcto, por lo que estamos viendo el enlace vinculado. El nodo tiene firmware para el nodo B , así que actualice B. | BD | D | |
| paso 4 | B tiene un hijo izquierdo, pero ya ha sido visitado. Así que imprimimos B , luego buscamos un hijo correcto, pero no lo hay, así que hacemos que el nodo cosido (es decir, A ) sea el actual. | BD | DB | |
| paso-5 | A tiene un hijo izquierdo B , pero ya ha sido visitado, por lo que imprimimos A y buscamos un hijo derecho. El nodo A tiene un hijo derecho C y no está en la lista de nodos visitados, por lo que lo agregamos a esta lista y lo hacemos actual. | bdc | administrador de bases de datos | |
| paso-6 | C tiene el nodo E como su hijo izquierdo y este nodo aún no ha sido visitado, así que agregue el nodo E a la lista y hágalo actual. | B D C E | DBA | |
| paso-7 | finalmente….. | D B A E C |