De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar
Algoritmos de búsqueda de gráficos y árboles
Listados
Temas relacionados
  • v
  • t
  • mi

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 (verificar y / o actualizar) cada nodo en una estructura de datos de árbol , exactamente una vez. Dichos 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 pueden generalizarse a otros árboles.

Tipos

A diferencia de las listas enlazadas , las matrices unidimensionales y otras estructuras de datos lineales , que se atraviesan canónicamente en orden lineal, los árboles se pueden atravesar de varias formas. Se pueden atravesar en primer orden en profundidad o en anchura . Hay tres formas comunes de atravesarlos en primer orden en 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 de profundidad limitada como búsqueda iterativa de profundización primero 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 el cruce de árboles

Atravesar un árbol implica iterar sobre todos los nodos de alguna manera. Debido a que de un nodo dado hay más de un posible siguiente nodo (no es una estructura de datos lineal), entonces, asumiendo el cálculo secuencial (no paralelo), algunos nodos deben ser diferidos, almacenados de alguna manera para una visita posterior. 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 recursivamente), el recorrido se puede definir mediante recursividad o, más sutilmente, correcursión , de una manera muy 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 profundidad se implementa fácilmente a través de una cola, incluido el núcleo de forma cursiva. [2] : 45−61

Búsqueda en profundidad del árbol binario

Travesía en profundidad (ruta de puntos) de un árbol binario:
  • Reserva (acceso al nodo en la posición roja ● ) :
        F, B, A, D, C, E, G, I, H;
  • En orden (acceso al nodo en la posición verde ● ) :
        A, B, C, D, E, F, G, H, I;
  • Pedido posterior (acceso al nodo en la posición azul ● ) :
        A, C, E, D, B, H, I, G, F.

Estas búsquedas se denominan búsqueda en profundidad primero (DFS), ya que el árbol de búsqueda se profundiza tanto como sea posible en cada niño antes de pasar al siguiente hermano. Para un árbol binario, se definen como operaciones de acceso en cada nodo, comenzando por el nodo actual, cuyo algoritmo es el siguiente: [3] [4]

El patrón recursivo general para atravesar un árbol binario es este:

  1. Bajar un nivel al argumento recursivo N . Si N existe (no está vacío), ejecute las siguientes tres operaciones en un orden determinado: [5]
    L: atraviesa de forma recursiva el subárbol izquierdo de N.
    R: atraviesa de forma recursiva el subárbol derecho de N.
    N: Acceda (visite) el propio nodo N actual .
  2. Regreso en subir un nivel y llegar al nodo principal del N .

Hay tres métodos (patrones) en los que la posición de los recorridos (recorrido) con respecto al nodo (en la figura: rojo, verde o azul) se llevará a cabo la visita (acceso) del nodo. La elección de exactamente un color determina exactamente una visita de un nodo como se describe a continuación. El acceso a los tres colores da como resultado una visita triple del mismo nodo que produce la secuenciación de "todo el orden":

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

  1. Acceda a la parte de datos del nodo actual (en la figura: posición roja).
  2. Atraviesa el subárbol izquierdo llamando de forma recursiva a la función de reserva.
  3. Atraviesa el subárbol derecho llamando de forma recursiva a la función de reserva.

El recorrido de preorden es uno ordenado topológicamente , porque un nodo padre se procesa antes de que se complete cualquiera de sus nodos secundarios.

Pedido posterior, LRN

  1. Atraviesa el subárbol izquierdo llamando de forma recursiva a la función posterior al pedido.
  2. Atraviesa el subárbol derecho llamando de forma recursiva a la función posterior al pedido.
  3. Acceda a la parte de datos del nodo actual (en la figura: posición azul).

La traza de un recorrido se denomina secuencialización del árbol. La traza transversal es una lista de cada nodo visitado. Ninguna secuenciación de acuerdo con el preorden, dentro o después del orden describe el árbol subyacente de forma única. Dado un árbol con elementos distintos, ya sea pre-pedido o post-pedido emparejado con en orden es suficiente para describir el árbol de manera única. Sin embargo, el pedido anticipado con el pedido posterior deja cierta ambigüedad en la estructura del árbol. [6]

En orden, LNR

  1. Atraviesa el subárbol izquierdo llamando de forma recursiva a la función en orden.
  2. Acceda a la parte de datos del nodo actual (en la figura: posición verde).
  3. Atraviesa el subárbol derecho llamando de forma recursiva a la función en orden.

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 ordenado. [7]

Invertir en orden, RNL

  1. Atraviese el subárbol derecho llamando de forma recursiva a la función inversa en orden.
  2. Accede a la parte de datos del nodo actual.
  3. Atraviese el subárbol izquierdo llamando de forma recursiva a la función inversa en orden.

En un árbol de búsqueda binaria , el recorrido inverso en orden recupera las claves en orden descendente .

Árbol genérico

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

  1. Si el nodo no está presente, regrese.
  2. Acceso (= visita) nodo (posición de pre-pedido).
  3. Para cada i de 1 a number_of_children - 1 hacer:
    1. Atraviesa recursivamente el i -ésimo hijo.
    2. Nodo de acceso (posición en orden).
  4. Atraviesa recursivamente al último hijo.
  5. Nodo de acceso (puesto post-pedido).

Dependiendo del problema en cuestión, las operaciones de preorden, posorden y especialmente una de las (número_de_niños - 1) en orden pueden ser anuladas, o se desea acceso solo a un niño específico, por lo que estas operaciones son opcionales. Además, en la práctica, es posible que se requiera más de una de las operaciones de preorden, en orden y posorder. Por ejemplo, cuando se inserta en un árbol ternario, se realiza una operación de reserva mediante la comparación de elementos. Es posible que se necesite una operación posterior al pedido para reequilibrar el árbol.

Búsqueda de amplitud o orden de nivel

Orden de nivel : F, B, G, A, D, I, C, E, H.

Los árboles también se pueden atravesar en orden de nivel , donde visitamos cada nodo en un nivel antes de ir a un nivel inferior. Esta búsqueda se conoce como búsqueda primero en amplitud (BFS), ya que el árbol de búsqueda se amplía tanto como sea posible en cada profundidad antes de pasar a la siguiente.

Otros tipos

También hay algoritmos de recorrido de árbol que no clasifican como búsqueda en profundidad ni como búsqueda en amplitud. Uno de esos algoritmos es la búsqueda de árboles 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

Árbol que representa la expresión aritmética: A * ( B - C ) + ( D + E )

El recorrido de pre-orden se puede usar para hacer una expresión de prefijo ( notación polaca ) a partir de árboles de expresión : recorra el árbol de expresión de manera pre-ordenada. Por ejemplo, atravesar la expresión aritmética representada en el pedido anticipado da como resultado "+ * A - B C + D E ".

El recorrido posterior al orden puede generar una representación de sufijo ( notación polaca inversa ) de un árbol binario. Al atravesar 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 en orden se usa con mucha frecuencia en árboles de búsqueda binaria porque devuelve valores del conjunto subyacente en orden, de acuerdo con el comparador que configuró el árbol de búsqueda binaria.

El recorrido posterior al pedido al eliminar o liberar nodos y valores puede eliminar o liberar un árbol binario completo. Por lo tanto, el nodo se libera después de liberar a sus hijos.

Además, la duplicación de un árbol binario produce una secuencia de acciones posterior al pedido, porque la copia del puntero a la copia de un nodo se asigna al campo hijo correspondiente N.child dentro de la copia del padre N inmediatamente después de la returncopia en el procedimiento recursivo. . Esto significa que el padre no puede terminar antes de que terminen todos los hijos.

Implementaciones

Búsqueda en profundidad

Reserva 

preorder (nodo) si (nodo == nulo ) volver visitar (nodo) preorder (node.left) preorder (node.right) 
iterativePreorder (nodo) if (nodo == nulo ) pila de retorno ← pila vacía stack.push (nodo) while ( no stack.isEmpty ()) nodo ← pila.pop () visitar (nodo) // el niño derecho se empuja primero para que el izquierdo se procese primero if node.right ≠ null stack.push (node.right) if node.left ≠ null stack.push (node.left)

Pedido posterior 

postorder (nodo) if (nodo == nulo ) volver postorder (node.left) postorder (node.right) visitar (nodo)
iterativePostorder (nodo) pila ← pila vacía lastNodeVisited ← nulo  while ( no pila.isEmpty () o nodo ≠ nulo ) if (nodo ≠ nulo ) stack.push (nodo) nodo ← nodo.izquierda demás peekNode ← stack.peek () // si el hijo derecho existe y atraviesa el nodo // del niño izquierdo, luego moverse a la derecha if (peekNode.right ≠ null  y lastNodeVisited ≠ peekNode.right) nodo ← peekNode.right demás visita (peekNode) lastNodeVisited ← stack.pop ()

En orden 

inorder (nodo) if (nodo == nulo ) volver inorder (nodo.izquierda) visitar (nodo) inorder (node.right)
iterativeInorder (nodo) pila ← pila vacía  while (nodo ≠ nulo  o  no pila.isEmpty ()) if (nodo ≠ nulo ) stack.push (nodo) nodo ← nodo.izquierda demás nodo ← pila.pop () visitar (nodo) nodo ← nodo.derecha

Único en orden

El nodo con el que se debe iniciar se encuentra a través de una función de búsqueda estándar , que se muestra aquí en una implementación sin punteros principales, es decir, utiliza una pila para contener a los padres. Del nodo resultante la función iterativeInorderUpwards devuelve el en-orden- suc cesador y la pila actualizado, de modo que el árbol puede ser secuencialmente buscaron más adelante.

El intercambio de izquierda a derecha daría como resultado una función que devuelve el predecesor en orden , digamos iterativeInorderDownwards .

(nodo, pila) ← búsqueda (árbol, clave) nodo ← árbol.root oldnode ← pila nula ← pila vacía  while (nodo ≠ nulo ) stack.push (nodo) nodo anterior ← nodo // guardar si clave <node.key nodo ← nodo.izquierda demás nodo ← nodo.derecha return (nodo antiguo, pila)
iterativeInorderUpwards (nodo, pila) nodo anterior ← nodo // guardar newnode ← node.right if (newnode ≠ null  while (newnode ≠ null ) nodo ← nuevonodo stack.push (nodo) newnode ← node.left return (nodo, pila) más newnode ← stack.pop () while ( no stack.isEmpty () y node = newnode.right) nodo ← nuevonodo newnode ← stack.pop () // ahora la pila está vacía // o nodo = newnode.left, es decir // newnode = sucesor (ancestro) del nodo return (nuevo nodo, pila)

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 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 subprocesando el árbol (siguiente sección).

Morris en orden transversal usando subprocesos

Un árbol binario se enhebra 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 a la orden sucesor del nodo (si existe).

Ventajas:

  1. Evita la recursividad, que usa una pila de llamadas y consume memoria y tiempo.
  2. El nodo mantiene un registro de su padre.

Desventajas:

  1. El árbol es más complejo.
  2. Solo podemos hacer un recorrido a la vez.
  3. Es más propenso a errores cuando ambos hijos 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: [8]

  1. Cree enlaces al sucesor en orden.
  2. Imprima los datos usando estos enlaces.
  3. Revertir los cambios para restaurar el árbol original.

Búsqueda de amplitud primero

Además, a continuación se incluye un pseudocódigo para un recorrido de orden de nivel basado en una cola simple , y requerirá un espacio proporcional al número máximo de nodos a una profundidad determinada. Esto puede ser tanto como el número total de nodos / 2. Se puede implementar un enfoque más eficiente en el espacio para este tipo de recorrido mediante una búsqueda iterativa de profundización primero en profundidad .

levelorder (raíz) q ← cola vacía q.enqueue (raíz) mientras  no q.isEmpty () hacer nodo ← q.dequeue () visitar (nodo) si node.left ≠ null  entonces q.enqueue (nodo.izquierda) si node.right ≠ null  entonces q.enqueue (node.right)

Árboles infinitos

Si bien el recorrido se realiza generalmente 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 hacer para árboles infinitos. Esto es de particular interés en la programación funcional (particularmente con la evaluación perezosa ), ya que a menudo se pueden definir y trabajar con estructuras de datos infinitas, 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 primero 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 posterior a la orden nunca lo hará. visitar cualquier nodo, ya que no ha llegado a una hoja (y de hecho nunca lo hará). Por el contrario, un recorrido en amplitud primero (orden de nivel) atravesará un árbol binario de profundidad infinita sin problemas y, de hecho, atravesará cualquier árbol con 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 primero visitará todos los nodos, ya que una vez agota a los nietos (hijos de hijos de un nodo), pasará al siguiente (suponiendo que no sea posterior a la orden, 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 a los hijos 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 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 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, rotula la raíz (), los hijos de la raíz (1), (2),…, los nietos (1, 1), (1, 2),…, (2 , 1), (2, 2),…, etc. Por lo tanto, los nodos están en una correspondencia uno a uno con secuencias finitas (posiblemente vacías) de números positivos, que son contables y se pueden colocar en orden primero por suma de entradas y luego por orden lexicográfico dentro de una suma dada (solo de manera finita 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:

  1. ()
  2. (1)
  3. (1, 1) (2)
  4. (1, 1, 1) (1, 2) (2, 1) (3)
  5. (1, 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 de amplitud primero: reemplace los bordes "hacia abajo" que conectan un nodo principal con su segundo hijo y posteriores con los bordes "derechos" 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 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).

Referencias

  1. ^ "Conferencia 8, recorrido del árbol" . Consultado el 2 de mayo de 2015 .
  2. ^ Pfaff, Ben (2004). Introducción a los árboles de búsqueda binaria y los árboles equilibrados . Fundación de Software Libre, Inc.
  3. ^ Métodos de recorrido de árbol binario
  4. ^ "Algoritmo de recorrido de pedidos anticipados" . Consultado el 2 de mayo de 2015 .
  5. ^ L antes de R significa el recorrido (estándar) en sentido antihorario, como en la figura.
    La ejecución de N antes, entre o después de L, R determina uno de los métodos descritos.
    Si el recorrido se toma al revés (en el sentido de las agujas del reloj), el recorrido se llama invertido. Esto se describe en particular para el orden inverso , cuando los datos deben recuperarse en orden descendente.
  6. ^ "Algoritmos, ¿qué combinaciones de secuencialización previa, posterior y en orden son únicas?" . Consultado el 2 de mayo de 2015 .
  7. ^ Wittman, Todd. "Recorrido del árbol" (PDF) . UCLA Math . Archivado desde el original (PDF) el 13 de febrero de 2015 . Consultado el 2 de enero de 2016 .
  8. ^ Morris, Joseph M. (1979). "Atravesar árboles binarios de forma sencilla y económica". Cartas de procesamiento de información . 9 (5). doi : 10.1016 / 0020-0190 (79) 90068-1 .

Fuentes

  • Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". DC Heath and Company. Lexington, MA. 1995. Cuarta edición.
  • Drozdek, Adam. "Estructuras de datos y algoritmos en C ++". Brook / Cole. Pacific Grove, CA. 2001. Segunda edición.
  • "Árbol transversal" (math.northwestern.edu)

Enlaces externos

  • Almacenamiento de datos jerárquicos en una base de datos con ejemplos transversales en PHP
  • Administrar datos jerárquicos en MySQL
  • Trabajar con gráficos en MySQL
  • Código de muestra para el recorrido de árbol recursivo e iterativo implementado en C.
  • Código de muestra para recorrido de árbol recursivo en Python.
  • Ver el cruce de árboles implementado en varios lenguajes de programación en Rosetta Code
  • Recorrido de árbol sin recursividad