Recorrido del árbol

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En informática, el recorrido de árboles (también conocido como búsqueda de árboles y caminar por el árbol) es una forma de recorrido de gráficos y se refiere a el proceso de visitar (por ejemplo, recuperar, actualizar o eliminar) cada nodo en una estructura de datos de árbol, exactamente una vez. Estos recorridos se clasifican según el orden en que se visitan los nodos. Los siguientes algoritmos se describen para un árbol binario, pero también se pueden generalizar a otros árboles.

Tipos

A diferencia de las listas enlazadas, los arreglos unidimensionales y otras estructuras de datos lineales, que canónicamente se recorren en orden lineal, los árboles se pueden recorrer de múltiples maneras. Se pueden recorrer en orden de profundidad o de anchura. Hay tres formas comunes de recorrerlos en orden de profundidad: en orden, en orden previo y en orden posterior. Más allá de estos recorridos básicos, son posibles varios esquemas más complejos o híbridos, como búsquedas de profundidad limitada como búsqueda iterativa de profundización en profundidad. Esta última, así como la búsqueda en amplitud, también se puede utilizar para atravesar árboles infinitos, ver más abajo.

Estructuras de datos para recorrido de árbol

Atravesar un árbol implica iterar sobre todos los nodos de alguna manera. Debido a que a partir de un nodo dado hay más de un nodo siguiente posible (no es una estructura de datos lineal), entonces, suponiendo un cálculo secuencial (no paralelo), algunos nodos deben diferirse, es decir, almacenarse de alguna manera para visitarlos más tarde. Esto suele hacerse mediante una pila (LIFO) o una cola (FIFO). Como un árbol es una estructura de datos autorreferencial (definida recursivamente), el recorrido se puede definir mediante recursividad o, más sutilmente, correcursión, de una manera natural y clara; en estos casos los nodos diferidos se almacenan implícitamente en la pila de llamadas.

La búsqueda en profundidad se implementa fácilmente a través de una pila, incluso de forma recursiva (a través de la pila de llamadas), mientras que la búsqueda en amplitud se implementa fácilmente a través de una cola, incluso de forma corecursiva.

Búsqueda en profundidad

En la búsqueda en profundidad (DFS), el árbol de búsqueda se profundiza tanto como sea posible antes de pasar al siguiente hermano.

Para recorrer árboles binarios con búsqueda en profundidad, realice las siguientes operaciones en cada nodo:

Si el nodo actual está vacío, entonces regrese.
Ejecutar las siguientes tres operaciones en un determinado orden:
N: Visita el nodo actual.
L: Recursively atraviesa el subárbol izquierdo del nodo actual.
R: Atravesando el subárbol derecho del nodo actual.

La traza de un recorrido se denomina secuencialización del árbol. El seguimiento transversal es una lista de cada nodo visitado. Ninguna secuencialización según orden anterior, posterior o posterior describe el árbol subyacente de forma única. Dado un árbol con elementos distintos, el orden previo o posterior combinado con el orden es suficiente para describir el árbol de forma única. Sin embargo, el pedido anticipado con el pedido posterior deja cierta ambigüedad en la estructura del árbol.

Existen tres métodos en qué posición del recorrido relativo al nodo (en la figura: rojo, verde o azul) se realizará la visita del nodo. La elección de exactamente un color determina exactamente una visita a un nodo como se describe a continuación. La visita a los tres colores da como resultado una visita triple al mismo nodo, lo que produce la secuencialización de "todos los pedidos":

F-B-A-A-A-B-D-C-C-C-D-E-E-E-D-B-F-G-G-I-H-H-H-I-I-G-F

Reserva, NLR

Visita el nodo actual (en la figura: rojo posición).
Recursivamente atraviesa el subárbol izquierdo del nodo actual.
Recursively atraviesa el subárbol derecho del nodo actual.

El recorrido de preorden está ordenado topológicamente, porque un nodo principal se procesa antes de que se realice cualquiera de sus nodos secundarios.

Post-orden, LRN

Recursivamente atraviesa el subárbol izquierdo del nodo actual.
Recursively atraviesa el subárbol derecho del nodo actual.
Visita el nodo actual (en la figura: posición azul).

El recorrido posterior al orden puede resultar útil para obtener la expresión postfija de un árbol de expresión binaria.

En orden, LNR

Recursivamente atraviesa el subárbol izquierdo del nodo actual.
Visita el nodo actual (en la figura: verde posición).
Recursively atraviesa el subárbol derecho del nodo actual.

En un árbol de búsqueda binario ordenado de manera que en cada nodo la clave sea mayor que todas las claves en su subárbol izquierdo y menor que todas las claves en su subárbol derecho, el recorrido en orden recupera las claves en ascendente orden ordenado.

Reserva inversa, NRL

Visita el nodo actual.
Recursively atraviesa el subárbol derecho del nodo actual.
Recursivamente atraviesa el subárbol izquierdo del nodo actual.

Post-orden inverso, RLN

Recursively atraviesa el subárbol derecho del nodo actual.
Recursivamente atraviesa el subárbol izquierdo del nodo actual.
Visita el nodo actual.

Orden inverso, RNL

Recursively atraviesa el subárbol derecho del nodo actual.
Visita el nodo actual.
Recursivamente atraviesa el subárbol izquierdo del nodo actual.

En un árbol de búsqueda binario ordenado de manera que en cada nodo la clave sea mayor que todas las claves en su subárbol izquierdo y menor que todas las claves en su subárbol derecho, el recorrido en orden inverso recupera las claves en descendente orden ordenado.

Árboles arbitrarios

Para recorrer árboles arbitrarios (no necesariamente árboles binarios) con búsqueda en profundidad, realice las siguientes operaciones en cada nodo:

Si el nodo actual está vacío, entonces regrese.
Visite el nodo actual para la traversal preordenada.
Para cada uno i del 1 al número actual de subárboles del nodo − 1, o de éste al primero para el traversal inverso, hacer:
1. Atravesando el nodo actual i- el subárbol.
2. Visite el nodo actual para la traversal en orden.
Recursively atraviesa el último subárbol del nodo actual.
Visita el nodo actual para la traversal post-orden.

Dependiendo del problema en cuestión, las operaciones de preorden, postorden y especialmente una de la cantidad de subárboles − 1 en orden pueden ser opcionales. Además, en la práctica puede ser necesaria más de una operación de preorden, postorden y en orden. Por ejemplo, al insertar en un árbol ternario, se realiza una operación de pedido anticipado comparando elementos. Es posible que sea necesaria una operación posterior al pedido para reequilibrar el árbol.

Búsqueda primero en amplitud

En la búsqueda primero en amplitud (BFS) o en la búsqueda por orden de niveles, el árbol de búsqueda se amplía tanto como sea posible antes de pasar a la siguiente profundidad.

Otros tipos

También existen algoritmos de recorrido de árbol que no se clasifican como búsqueda en profundidad ni en amplitud. Uno de esos algoritmos es la búsqueda en árbol de Monte Carlo, que se concentra en analizar los movimientos más prometedores, basando la expansión del árbol de búsqueda en un muestreo aleatorio del espacio de búsqueda.

Aplicaciones

El recorrido de preorden se puede utilizar para crear una expresión de prefijo (notación polaca) a partir de árboles de expresión: recorra el árbol de expresión de forma preordenada. Por ejemplo, al recorrer la expresión aritmética representada en el pedido anticipado se obtiene "+ * A − B C + D E". En notación de prefijo, no hay necesidad de paréntesis siempre que cada operador tenga un número fijo de operandos. El recorrido de pedido anticipado también se utiliza para crear una copia del árbol.

El recorrido posterior al orden puede generar una representación de sufijo (notación polaca inversa) de un árbol binario. Al recorrer la expresión aritmética representada en el orden posterior se obtiene "A B C − * D E + +"; este último se puede transformar fácilmente en código de máquina para evaluar la expresión mediante una máquina de pila. El recorrido posterior al pedido también se utiliza para eliminar el árbol. Cada nodo se libera después de liberar a sus hijos.

El recorrido en orden se usa muy comúnmente en árboles de búsqueda binarios porque devuelve valores del conjunto subyacente en orden, según el comparador que configuró el árbol de búsqueda binario.

Implementaciones

Implementación de búsqueda en profundidad

Implementación de pedidos anticipados

procedimiento preorder(nodo)
 si nodo = nulo Regresovisita(nodo)
preorder(node.left)
preorder(node.right)

procedimiento iterativePreorder(nodo)
 si nodo = nulo Regresopila ← pila vacíastack.push(nodo)
 mientras no stack.isEmpty()
nodo ← pila.pop()
visita(nodo)
// el niño derecho es empujado primero para que la izquierda se procesa primero
 si node.right ل nulostack.push(node.right)
 si node.left nulostack.push(node.left)

Implementación posterior al pedido

procedimiento postorder(nodo)
 si nodo = nulo Regresopostorder(node.left)
postorder(node.right)
visita(nodo)

procedimiento iterativa Postorder(nodo)
pila ← pila vacíaúltimo NodeVisited ← nulo mientras no stack.isEmpty() o nodo nulo si nodo nulostack.push(nodo)
nodo ← nodo. izquierda
 máspeekNode ← stack.peek()
// si el niño adecuado existe y atraviesa el nodo
// desde el niño izquierdo, luego moverse a la derecha
 si peekNode.right √ nulo y último Node Visitado ل peekNode.right
nodo ← peekNode.right
 másvisit(peekNode)
lastNodeVisited ← stack.pop()

Implementación en orden

procedimiento inorder(nodo)
 si nodo = nulo Regresoinorder(node.left)
visita(nodo)
inorder(node.right)

procedimiento iterativeInorder(nodo)
pila ← pila vacía mientras no stack.isEmpty() o nodo nulo si nodo nulostack.push(nodo)
nodo ← nodo. izquierda
 másnodo ← pila.pop()
visita(nodo)
nodo ← nodo. derecho

Otra variante de Pre-order

Si el árbol está representado por una matriz (el primer índice es 0), es posible calcular el índice del siguiente elemento:

procedimiento burbuja (array, i, hoja)
k ← 1
i ← (i - 1)/2
 mientras (página + 1) % (k * 2)
i ← (i - 1)/2
k ← 2
 Regreso i

procedimiento preorder(arriba)
i ← 0
 mientras i √ array.size
visit(array[i])
 si i = tamaño - 1
i ← tamaño
 si i) tamaño/2
i ← i 2 + 1
 más← i - tamaño/2
padre ← burbuja_up (array, i, hoja)
i ← padre * 2 + 2

Avanzar al nodo siguiente o anterior

El nodo con el que se va a iniciar puede haberse encontrado en el árbol de búsqueda binaria bst mediante una función de búsqueda estándar, que es se muestra aquí en una implementación sin punteros principales, es decir, utiliza una stack para contener los punteros ancestrales.

procedimiento search(bst, key)
// devuelve un (nodo, pila)
nodo ← bst.root
pila ← pila vacía mientras nodo nulostack.push(nodo)
 si llave = nodo. clave
 Regreso (nodo, pila)
 si llave nodo. clave
nodo ← nodo. izquierda
 másnodo ← nodo. derecho
 Regreso ()nulo, pila vacía)

La función inorderNext devuelve un vecino en orden de nodo, ya sea el in-order-successor (para dir=1) o el en-orden-predecessor (para < code>dir=0) y la stack actualizada, de modo que el árbol de búsqueda binaria pueda recorrerse secuencialmente en orden y buscarse en la dirección dada dir > más adelante.

procedimiento inorderNext(node, dir, stack)
newnode ← node.child[dir]
 si newnode √ nulo donodo ← newnode
stack.push(nodo)
newnode ← node.child[1-dir]
 hasta newnode = nulo Regreso (nodo, pila)
// nodo no tiene un niño dir:
 do si stack.isEmpty()
 Regreso ()nulo, pila vacía)
nodo ← nodo
nodo ← pila.pop() // padre de los viejos
 hasta oldnode ‡ node.child[dir]
// now oldnode = node.child[1-dir],
// i.e. node = ancestro (y predecesor/éctor) del nodo original
 Regreso (nodo, pila)

Tenga en cuenta que la función no utiliza llaves, lo que significa que la estructura secuencial está completamente grabada por los bordes del árbol de búsqueda binario. Para los traversales sin cambio de dirección, la complejidad media (amortizada) es ${displaystyle {mathcal {}(1),}$ porque un traversal completo toma ${displaystyle 2n-2}$ pasos para un BST de tamaño ${displaystyle n,}$ 1 paso para el borde arriba y 1 para el borde hacia abajo. La peor complejidad es ${displaystyle {Mathcal}(h)}$ con ${displaystyle h}$ como la altura del árbol.

Todas las implementaciones anteriores requieren un espacio de pila proporcional a la altura del árbol, que es una pila de llamadas para los recursivos y una pila principal (antepasada) para los iterativos. En un árbol mal equilibrado, esto puede ser considerable. Con las implementaciones iterativas podemos eliminar el requisito de la pila manteniendo los punteros principales en cada nodo o enhebrando el árbol (siguiente sección).

Recorrido en orden de Morris usando subprocesos

Un árbol binario se estructura haciendo que cada puntero secundario izquierdo (que de otro modo sería nulo) apunte al predecesor en orden del nodo (si existe) y cada puntero secundario derecho (que de otro modo sería nulo) apunte a el sucesor en orden del nodo (si existe).

Ventajas:

Evita la recursión, que utiliza una pila de llamadas y consume memoria y tiempo.
El nodo guarda un registro de su padre.

Desventajas:

El árbol es más complejo.
Sólo podemos hacer un traversal a la vez.
Es más propenso a los errores cuando ambos niños no están presentes y ambos valores de nodos apuntan a sus antepasados.

El recorrido de Morris es una implementación del recorrido en orden que utiliza subprocesos:

Crear enlaces al sucesor en el orden.
Imprima los datos usando estos enlaces.
Revertir los cambios para restaurar el árbol original.

Búsqueda primero en amplitud

Además, a continuación se enumera el pseudocódigo para un recorrido de orden de nivel basado en cola simple, y requerirá un espacio proporcional al número máximo de nodos en una profundidad determinada. Esto puede representar hasta la mitad del número total de nodos. Se puede implementar un enfoque más eficiente en términos de espacio para este tipo de recorrido mediante una búsqueda iterativa de profundización primero en profundidad.

procedimiento nivelorder(nodo)
queue ← vacía queuequeue.enqueue(node)
 mientras no queue.isEmpty()
nodo ← queue.dequeue()
visita(nodo)
 si node.left nuloqueue.enqueue(node.left)
 si node.right ل nuloqueue.enqueue(node.right)

Si el árbol está representado por una matriz (el primer índice es 0), es suficiente iterar a través de todos los elementos:

procedimiento nivelorder(arriba)
 para i desde 0 a array.size
visit(array[i])

Árboles infinitos

Si bien el recorrido generalmente se realiza para árboles con un número finito de nodos (y, por lo tanto, una profundidad finita y un factor de ramificación finito), también se puede realizar para árboles infinitos. Esto es de particular interés en la programación funcional (particularmente con evaluación diferida), ya que a menudo se pueden definir y trabajar fácilmente con infinitas estructuras de datos, aunque no se evalúan (estrictamente), ya que esto llevaría un tiempo infinito. Algunos árboles finitos son demasiado grandes para representarlos explícitamente, como el árbol del juego de ajedrez o go, por lo que es útil analizarlos como si fueran infinitos.

Un requisito básico para el recorrido es visitar todos los nodos eventualmente. Para árboles infinitos, los algoritmos simples a menudo fallan en esto. Por ejemplo, dado un árbol binario de profundidad infinita, una búsqueda en profundidad descenderá por un lado (por convención, el lado izquierdo) del árbol, sin visitar nunca el resto y, de hecho, un recorrido en orden o post-orden nunca lo hará. visite cualquier nodo, ya que no ha llegado a una hoja (y de hecho nunca lo hará). Por el contrario, un recorrido de amplitud primero (orden de nivel) atravesará un árbol binario de profundidad infinita sin problemas y, de hecho, atravesará cualquier árbol con un factor de ramificación acotado.

Por otro lado, dado un árbol de profundidad 2, donde la raíz tiene infinitos hijos, y cada uno de estos hijos tiene dos hijos, una búsqueda en profundidad visitará todos los nodos, ya que una vez que agote los nietos (hijos de hijos de un nodo), pasará al siguiente (asumiendo que no es post-orden, en cuyo caso nunca llega a la raíz). Por el contrario, una búsqueda amplia nunca llegará a los nietos, ya que busca agotar a los niños primero.

Se puede realizar un análisis más sofisticado del tiempo de ejecución mediante infinitos números ordinales; por ejemplo, la búsqueda en amplitud del árbol de profundidad 2 anterior tomará ω·2 pasos: ω para el primer nivel y luego otro ω para el segundo nivel.

Por lo tanto, las búsquedas simples en profundidad o en amplitud no atraviesan todos los árboles infinitos y no son eficientes en árboles muy grandes. Sin embargo, los métodos híbridos pueden atravesar cualquier árbol (contablemente) infinito, esencialmente a través de un argumento diagonal ("diagonal", una combinación de vertical y horizontal, corresponde a una combinación de profundidad y amplitud).

Concretamente, dado el árbol infinitamente ramificado y de profundidad infinita, etiquetar la raíz (), los hijos de la raíz (1), (2),..., los nietos (1, 1), (1, 2),..., (2, 1), (2, 2),..., y así sucesivamente. Los nodos están, por tanto, en correspondencia uno a uno con secuencias finitas (posiblemente vacías) de números positivos, que son contables y pueden ordenarse primero por suma de entradas y luego por orden lexicográfico dentro de una suma dada (sólo finitamente). muchas secuencias suman un valor dado, por lo que se alcanzan todas las entradas; formalmente hay un número finito de composiciones de un número natural dado, específicamente 2ⁿ⁻¹ composiciones de < span class="nowrap">n ≥ 1), lo que da un recorrido. Explícitamente:

()
1)
(1, 1) 2)
(1, 1, 1) (1, 2) (2, 1) 3)
(1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 4)

etc.

Esto se puede interpretar como mapear el árbol binario de profundidad infinita en este árbol y luego aplicar la búsqueda en amplitud: reemplazar el valor "abajo" bordes que conectan un nodo padre con su segundo y posteriores hijos con bordes "derechos" bordes del primer hijo al segundo hijo, del segundo hijo al tercer hijo, etc. Por lo tanto, en cada paso uno puede bajar (agregar un (, 1) al final) o ir a la derecha (agregar uno al último número) (excepto la raíz, que es extra y sólo puede bajar), que muestra la correspondencia entre el árbol binario infinito y la numeración anterior; la suma de las entradas (menos uno) corresponde a la distancia desde la raíz, que concuerda con los 2ⁿ⁻¹ nodos en la profundidad n − 1 en el árbol binario infinito (2 corresponde a binario).

Contenido relacionado

Más resultados...