En informática , el recorrido de un árbol (también conocido como búsqueda de árbol y recorrido por el árbol ) es una forma de recorrido de grafos 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. Dichos recorridos se clasifican según el orden en el 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 , las matrices unidimensionales y otras estructuras de datos lineales , que se recorren canónicamente en orden lineal, los árboles se pueden recorrer de múltiples formas. Se pueden recorrer en orden de profundidad o de amplitud . Hay tres formas comunes de recorrerlos en orden de profundidad: en orden, preorden y posorden. [1] Más allá de estos recorridos básicos, son posibles varios esquemas más complejos o híbridos, como búsquedas limitadas en profundidad como la búsqueda en profundidad de profundización iterativa . Esta última, así como la búsqueda en amplitud, también se puede utilizar para recorrer árboles infinitos, consulte a continuación.
Para recorrer un árbol es necesario 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 se hace a menudo a través de una pila (LIFO) o una cola (FIFO). Como un árbol es una estructura de datos autorreferencial (definida de forma recursiva), el recorrido puede definirse por recursión o, más sutilmente, por 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 recursiva. [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. La traza del recorrido es una lista de cada nodo visitado. Ninguna secuenciación según el orden previo, interno o posterior describe el árbol subyacente de forma única. Dado un árbol con elementos distintos, tanto el orden previo como el posterior emparejados con el interno son suficientes para describir el árbol de forma única. Sin embargo, el orden previo con el posterior deja cierta ambigüedad en la estructura del árbol. [6]
Existen tres métodos en los que la posición del recorrido en relación con el nodo (en la figura: rojo, verde o azul) debe tener lugar la visita al nodo. La elección de exactamente un color determina exactamente una visita a un nodo, como se describe a continuación. La visita en los tres colores da como resultado una visita triple del mismo nodo, lo que produce la secuencialización de "todo orden":
El recorrido en preorden está ordenado topológicamente , porque un nodo padre se procesa antes de que lo haga cualquiera de sus nodos hijos.
El recorrido post-orden puede ser útil para obtener la expresión postfija de un árbol de expresión binaria .
En un árbol de búsqueda binario ordenado de tal manera que en cada nodo la clave es 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 orden ascendente . [7]
En un árbol de búsqueda binario ordenado de tal manera que en cada nodo la clave es mayor que todas las claves en su subárbol izquierdo y menor que todas las claves en su subárbol derecho, el recorrido inverso en orden recupera las claves en orden ordenado descendente .
Para recorrer á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, posorden y, especialmente, una de las operaciones de subárboles − 1 en orden pueden ser opcionales. Además, en la práctica, pueden requerirse más de una operación de preorden, posorden y en orden. Por ejemplo, al insertar en un árbol ternario, se realiza una operación de preorden comparando elementos. Puede ser necesaria una operación de posorden después para reequilibrar el árbol.
En la búsqueda en amplitud (BFS) o 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 árboles que no se clasifican como búsquedas en profundidad ni en amplitud. Uno de estos algoritmos es la búsqueda en árbol de Monte Carlo , que se concentra en analizar los movimientos más prometedores y basa la expansión del árbol de búsqueda en un muestreo aleatorio del espacio de búsqueda.
El recorrido en 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 en preorden. Por ejemplo, al recorrer la expresión aritmética representada en preorden se obtiene "+ * A − B C + D E ". En la notación de prefijo, no hay necesidad de paréntesis siempre que cada operador tenga un número fijo de operandos. El recorrido en preorden también se utiliza para crear una copia del árbol.
El recorrido en posorden puede generar una representación posfija ( notación polaca inversa ) de un árbol binario. Al recorrer la expresión aritmética representada en posorden 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 en posorden también se utiliza para eliminar el árbol. Cada nodo se libera después de liberar a sus hijos.
El recorrido en orden se utiliza muy comúnmente en árboles de búsqueda binaria porque devuelve valores del conjunto subyacente en orden, según el comparador que configuró el árbol de búsqueda binaria.
Si el árbol está representado por una matriz (el primer índice es 0), es posible calcular el índice del siguiente elemento: [8] [ aclaración necesaria ]
procedimiento bubbleUp(matriz, i, hoja) k ← 1 yo ← (yo - 1)/2 mientras (hoja + 1) % (k * 2) ≠ k yo ← (yo - 1)/2 k ← 2 * k devuelvo yoprocedimiento preordenar(matriz) yo ← 0 mientras i ≠ array.size visita(matriz[i]) si i = tamaño - 1 yo ← tamaño De lo contrario, si i < tamaño/2 yo ← yo * 2 + 1 demás hoja ← i - tamaño/2 padre ← bubble_up(matriz, i, hoja) i ← padre * 2 + 2
Es posible que el elemento nodecon el que se debe iniciar se haya encontrado en el árbol de búsqueda binaria bstmediante una función de búsqueda estándar , que se muestra aquí en una implementación sin punteros padre, es decir, utiliza un stackpara almacenar los punteros antecesores.
procedimiento de búsqueda(bst, clave) // devuelve un (nodo, pila) nodo ← bst.root pila ← pila vacía mientras nodo ≠ nulo pila.push(nodo) si clave = nodo.clave devuelve (nodo, pila) si clave < nodo.clave nodo ← nodo.izquierda demás nodo ← nodo.derecho retorna ( 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 binario pueda recorrerse secuencialmente en orden y buscarse en la dirección dada dirmás adelante.
procedimiento inorderNext(nodo, dir, pila) nuevo nodo ← nodo.hijo[dir] si newnode ≠ null hacer nodo ← nuevonodo pila.push(nodo) nuevo nodo ← nodo.hijo[1-dir] hasta que newnode = null devuelva (nodo, pila) // el nodo no tiene un directorio secundario: hacer si stack.isEmpty() return ( null , pila vacía ) nodo antiguo ← nodo nodo ← stack.pop() // padre de oldnode hasta que oldnode ≠ node.child[dir] // ahora oldnode = node.child[1-dir], // ie 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 está completamente registrada por los bordes del árbol de búsqueda binaria. Para los recorridos sin cambio de dirección, la complejidad promedio ( amortizada ) se debe a que un recorrido completo requiere pasos para un BST de tamaño 1 paso para el borde hacia arriba y 1 para el borde hacia abajo. La complejidad del peor caso es con 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 las recursivas y una pila padre (antepasada) para las iterativas. En un árbol mal equilibrado, esto puede ser considerable. Con las implementaciones iterativas podemos eliminar el requisito de pila manteniendo punteros padre en cada nodo o enhebrando el árbol (siguiente sección).
Un árbol binario se crea haciendo que cada puntero hijo izquierdo (que de otro modo sería nulo) apunte al predecesor en orden del nodo (si existe) y cada puntero hijo derecho (que de otro modo sería nulo) apunte al sucesor en orden 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 incluye un pseudocódigo para un recorrido simple por orden de nivel basado en colas , y requerirá un espacio proporcional al número máximo de nodos a una profundidad determinada. Esto puede ser hasta la mitad del número total de nodos. Se puede implementar un enfoque más eficiente en cuanto al espacio para este tipo de recorrido utilizando una búsqueda iterativa de profundidad en primer lugar .
nivel de procedimientoorder (nodo) cola ← cola vacía cola.enqueue(nodo) mientras no esté en cola.isEmpty() nodo ← cola.dequeue() visita(nodo) si nodo.izquierda ≠ nulo cola.poner en cola(nodo.izquierda) si nodo.derecho ≠ nulo cola.poner en cola(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:
procedimiento levelorder(array) para i desde 0 hasta array.size visita(matriz[i])
Si bien el recorrido se realiza generalmente para árboles con un número finito de nodos (y, por lo tanto, profundidad finita y 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 las estructuras de datos infinitas a menudo se pueden definir y trabajar fácilmente, aunque no se evalúen (estrictamente), ya que esto llevaría un tiempo infinito. Algunos árboles finitos son demasiado grandes para representarlos explícitamente, como el árbol de juegos para 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 no lo logran. Por ejemplo, dado un árbol binario de profundidad infinita, una búsqueda en profundidad se dirigirá hacia abajo 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 visitará ningún nodo, ya que no ha llegado a una hoja (y de hecho nunca lo hará). Por el contrario, un recorrido en amplitud (orden de nivel) recorrerá un árbol binario de profundidad infinita sin problemas, y de hecho recorrerá cualquier árbol con un factor de ramificación acotado.
Por otra parte, 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 los hijos de un nodo), pasará al siguiente (suponiendo que no sea de orden posterior, en cuyo caso nunca llega a la raíz). Por el contrario, una búsqueda en amplitud nunca llegará a los nietos, ya que busca agotar primero a los hijos.
Se puede realizar un análisis más sofisticado del tiempo de ejecución mediante números ordinales infinitos ; 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 recorren todos los árboles infinitos y no son eficientes en árboles muy grandes. Sin embargo, los métodos híbridos pueden recorrer cualquier árbol infinito (contable), 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 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 lo tanto, en una correspondencia biunívoca con secuencias finitas (posiblemente vacías) de números positivos, que son contables y pueden colocarse en orden primero por suma de entradas, y luego por orden lexicográfico dentro de una suma dada (solo un número finito de 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 puede interpretarse como mapear el árbol binario de profundidad infinita en este árbol y luego aplicar la búsqueda en amplitud: reemplazar los bordes "hacia abajo" que conectan un nodo padre a su segundo y posteriores hijos con bordes "hacia la derecha" del primer hijo al segundo hijo, del segundo hijo al tercer hijo, etc. Así, en cada paso, uno puede ir hacia abajo (agregar un (, 1) al final) o ir a la derecha (agregar uno al último número) (excepto la raíz, que es adicional y solo puede ir hacia abajo), lo 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).
