En informática , el recorrido de árbol (también conocido como búsqueda de árbol y caminar por el árbol ) es una forma de recorrido de gráfico y se refiere al 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.
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 atravesar 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. [1] 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.
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 adelante. 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, corecursió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. [2] : 45-61
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: [3] [4]
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. [6]
Hay tres métodos en qué posición del recorrido con respecto 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":
El recorrido de preorden está ordenado topológicamente , porque un nodo principal se procesa antes de que se realice cualquiera de sus nodos secundarios.
El recorrido posterior al orden puede resultar útil para obtener la expresión postfija de un árbol de expresión binaria .
En un árbol de búsqueda binario ordenado de manera que en cada nodo la clave sea mayor que todas las claves de su subárbol izquierdo y menor que todas las claves de su subárbol derecho, el recorrido en orden recupera las claves en orden ascendente . [7]
En un árbol de búsqueda binario ordenado de modo que en cada nodo la clave sea mayor que todas las claves de su subárbol izquierdo y menor que todas las claves de su subárbol derecho, el recorrido en orden inverso recupera las claves en orden descendente .
Para atravesar árboles arbitrarios (no necesariamente árboles binarios) con búsqueda en profundidad, realice las siguientes operaciones en cada nodo:
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.
En la búsqueda en amplitud (BFS) o en la búsqueda por orden de nivel , el árbol de búsqueda se amplía tanto como sea posible antes de pasar a la siguiente profundidad.
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 de á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.
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 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.
Si el árbol está representado por una matriz (el primer índice es 0), es posible calcular el índice del siguiente elemento: [8] [ se necesita aclaración ]
procedimiento bubbleUp(matriz, i, hoja) k ← 1 yo ← (yo - 1)/2 mientras (hoja + 1) % (k * 2) ≠ k yo ← (yo - 1)/2 k ← 2 * k volver yoorden previa del procedimiento (matriz) yo ← 0 mientras que yo ≠ matriz.tamaño visita (matriz [i]) si i = tamaño - 1 yo ← tamaño si no, si <tamaño/2 yo ← yo * 2 + 1 demás hoja ← i - tamaño/2 padre ← bubble_up(matriz, i, hoja) yo ← padre * 2 + 2
Es posible que el objeto nodecon el que se va a empezar se haya encontrado en el árbol de búsqueda binario bstmediante una función de búsqueda estándar , que se muestra aquí en una implementación sin punteros principales, es decir, utiliza un stackpara guardar los punteros ancestrales.
búsqueda de procedimientos (bst, clave) // devuelve un (nodo, pila) nodo ← bst.root pila ← pila vacía mientras nodo ≠ nulo pila.push(nodo) if clave = nodo.key return (nodo, pila) if key < nodo.key nodo ← nodo.izquierda demás nodo ← nodo.derecha retorno ( nulo , pila vacía )
La función inorderNext [2] : 60 devuelve un vecino en orden de node, ya sea el sucesor en orden (para dir=1) o el predecesor en orden (para )dir=0 , y el actualizado stack, de modo que el árbol de búsqueda binaria se puede recorrer secuencialmente en orden y buscar en la dirección dada dirmás adelante.
procedimiento inorderNext(nodo, directorio, pila) nuevonodo ← nodo.niño[dir] si nuevonodo ≠ nulo hacer nodo ← nuevo nodo pila.push(nodo) nuevonodo ← nodo.niño[1-dir] hasta newnode = null retorno (nodo, pila) // el nodo no tiene un directorio secundario: hazlo si stack.isEmpty() regresa ( nulo , pila vacía ) nodo antiguo ← nodo nodo ← stack.pop() // padre del nodo antiguo hasta oldnode ≠ node.child[dir] // ahora nodoantiguo = nodo.niño[1-dir], // es decir, nodo = ancestro (y predecesor/sucesor) del nodo original retorno (nodo, pila)
Tenga en cuenta que la función no utiliza claves, lo que significa que la estructura secuencial queda completamente registrada por los bordes del árbol de búsqueda binaria. Para recorridos sin cambio de dirección, la complejidad promedio ( amortizada ) se debe a que un recorrido completo toma pasos para un BST de tamaño 1 paso para el borde ascendente y 1 para el borde descendente. La complejidad del peor de los casos es 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).
Un árbol binario se enhebra 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 al in- orden sucesor del nodo (si existe).
Ventajas:
Desventajas:
El recorrido de Morris es una implementación del recorrido en orden que utiliza subprocesos: [9]
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 .
orden de nivel de procedimiento (nodo) cola ← cola vacía cola.encola(nodo) mientras no queue.isEmpty() nodo ← cola.dequeue() visita (nodo) si nodo.izquierda ≠ nulo cola.encola(nodo.izquierda) si nodo.derecho ≠ nulo cola.encola(nodo.derecha)
Si el árbol está representado por una matriz (el primer índice es 0), es suficiente iterar a través de todos los elementos:
orden de nivel del procedimiento (matriz) para i de 0 a matriz.tamaño visita (matriz [i])
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 eventualmente todos los nodos. 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 agotados 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 primero en profundidad o primero 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, etiquete 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 n −1 composiciones de n ≥ 1 ), lo que da un recorrido. Explícitamente:
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 los bordes "abajo" que conectan un nodo padre con su segundo y posteriores hijos con bordes "derechos" desde el primer hijo hasta el segundo. hijo, del segundo hijo al tercer hijo, etc. Así, en cada paso uno puede bajar (añadir un (, 1) al final) o ir a la derecha (añadir uno al último número) (excepto la raíz, que es extra y solo 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 n −1 nodos en la profundidad n − 1 en el árbol binario infinito (2 corresponde a binario).
