Hispanopedia Wiki
Articulo de referencia

Recorrido de árboles

En informática , el recorrido de árboles (también conocido como búsqueda en árboles o exploración de árboles ) es una forma de recorrido de grafos y se refiere al proceso de vis...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el recorrido de árboles (también conocido como búsqueda en árboles o exploración de árboles ) 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 que se visitan los nodos. Los siguientes algoritmos se describen para un árbol binario , pero pueden generalizarse a otros tipos de árboles.

Tipos

0

Método de recorrido: 1
Nodo anterior Reiniciar Inicio
Una demostración interactiva de diferentes métodos de recorrido de árboles.

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

Estructuras de datos para el recorrido de árboles

Recorrer un árbol implica iterar sobre todos los nodos de alguna manera. Dado que desde un nodo dado hay más de un nodo siguiente posible (no es una estructura de datos lineal), entonces, asumiendo una computación secuencial (no paralela), algunos nodos deben diferirse, almacenándose de alguna manera para su posterior visita. Esto se suele hacer mediante una pila (LIFO) o una cola (FIFO). Como un árbol es una estructura de datos autorreferencial (definida recursivamente), el recorrido puede definirse mediante recursión o, de forma más sutil, mediante corecursión , de 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 mediante 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 mediante una cola, incluso de forma corecursiva. [ 2 ] : 45−61

En la búsqueda en profundidad (DFS), el árbol de búsqueda se profundiza lo máximo posible antes de pasar al siguiente elemento hermano.

Para recorrer árboles binarios con búsqueda en profundidad, se realizan las siguientes operaciones en cada nodo: [ 3 ] [ 4 ]

  1. Si el nodo actual está vacío, entonces regresa.
  2. Ejecuta las siguientes tres operaciones en un orden determinado: [ 5 ]
    N: Visita el nodo actual.
    L: Recorre recursivamente el subárbol izquierdo del nodo actual.
    R: Recorre recursivamente el subárbol derecho del nodo actual.

El rastro de un recorrido se denomina secuenciación del árbol. El rastro del recorrido es una lista de cada nodo visitado. Ninguna secuenciación, ya sea en preorden, en orden o en postorden, describe el árbol subyacente de forma unívoca. Dado un árbol con elementos distintos, tanto el preorden como el postorden, combinados con el orden, son suficientes para describir el árbol de forma unívoca. Sin embargo, la combinación de preorden y postorden introduce cierta ambigüedad en la estructura del árbol. [ 6 ]

Existen tres métodos para determinar la posición del recorrido con respecto al nodo (en la figura: rojo, verde o azul) en la que se realizará la visita al nodo. La elección de un solo color determina una única visita al nodo, como se describe a continuación. La visita a través de los tres colores da como resultado una triple visita al mismo nodo, lo que produce la secuenciación en "todo 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
Recorrido en profundidad (ruta punteada) de un árbol binario:

Reserva anticipada, NLR

  1. Visite el nodo actual (en la figura: posición roja).
  2. Recorre recursivamente el subárbol izquierdo del nodo actual.
  3. Recorre recursivamente el subárbol derecho del nodo actual.

El recorrido en preorden es un recorrido ordenado topológicamente , porque un nodo padre se procesa antes de que se haya procesado cualquiera de sus nodos hijos.

Pedido posterior, LRN

  1. Recorre recursivamente el subárbol izquierdo del nodo actual.
  2. Recorre recursivamente el subárbol derecho del nodo actual.
  3. Visite el nodo actual (en la figura: posición azul).

El recorrido en postorden puede ser útil para obtener la expresión postfija de un árbol de expresiones binarias .

En orden, LNR

  1. Recorre recursivamente el subárbol izquierdo del nodo actual.
  2. Visite el nodo actual (en la figura: posición verde).
  3. Recorre recursivamente el subárbol derecho del nodo actual.

En un árbol de búsqueda binaria ordenado de tal manera que en cada nodo la clave es 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 ]

Reserva inversa, NRL

  1. Visita el nodo actual.
  2. Recorre recursivamente el subárbol derecho del nodo actual.
  3. Recorre recursivamente el subárbol izquierdo del nodo actual.

Pedido posterior inverso, RLN

  1. Recorre recursivamente el subárbol derecho del nodo actual.
  2. Recorre recursivamente el subárbol izquierdo del nodo actual.
  3. Visita el nodo actual.

Regreso en orden inverso, RNL

  1. Recorre recursivamente el subárbol derecho del nodo actual.
  2. Visita el nodo actual.
  3. Recorre recursivamente el subárbol izquierdo del nodo actual.

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

Árboles arbitrarios

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

  1. Si el nodo actual está vacío, entonces regresa.
  2. Visite el nodo actual para realizar un recorrido en preorden.
  3. Para cada i desde 1 hasta el número de subárboles del nodo actual − 1, o desde este último hasta el primero para el recorrido inverso, haga lo siguiente:
    1. Recorre recursivamente el i -ésimo subárbol del nodo actual.
    2. Visite el nodo actual para realizar un recorrido en orden.
  4. Recorre recursivamente el último subárbol del nodo actual.
  5. Visite el nodo actual para realizar un recorrido en postorden.

Dependiendo del problema en cuestión, las operaciones en preorden, postorden y, especialmente, una de las operaciones en orden (número de subárboles menos uno) pueden ser opcionales. Además, en la práctica, puede ser necesario realizar más de una de estas operaciones. Por ejemplo, al insertar en un árbol ternario, se realiza una operación en preorden comparando los elementos. Posteriormente, puede ser necesaria una operación en postorden para reequilibrar el árbol.

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

En la búsqueda en amplitud (BFS) o búsqueda por 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 árboles que no se clasifican ni como búsqueda en profundidad ni como búsqueda en amplitud. Un ejemplo de ello es la búsqueda en árbol de Monte Carlo , que se centra 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 en preorden se puede utilizar para crear una expresión prefija ( notación polaca ) a partir de árboles de expresiones : se recorre el árbol de expresiones en preorden. Por ejemplo, recorrer la expresión aritmética representada en preorden produce "+ * A − B C + D E ". En notación prefija, no se necesitan 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 postorden puede generar una representación postfija ( notación polaca inversa ) de un árbol binario. Recorrer la expresión aritmética representada en postorden produce " A B C − * D E + +"; esta última se puede transformar fácilmente en código máquina para evaluar la expresión mediante una máquina de pila . El recorrido en postorden 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 con mucha frecuencia en los árboles de búsqueda binaria porque devuelve los valores del conjunto subyacente en orden, según el comparador que configuró el árbol de búsqueda binaria.

Implementaciones

Implementación de búsqueda en profundidad

A continuación se muestran ejemplos de implementación basada en pilas para el recorrido en preorden, postorden e inorden en un enfoque recursivo (izquierda) y en un enfoque iterativo (derecha).

Las implementaciones mediante un enfoque iterativo permiten evitar los inconvenientes de la recursión , en particular las limitaciones de espacio en la pila y los problemas de rendimiento.

También se mencionan varias implementaciones alternativas.

Implementación de pedidos anticipados

Implementación posterior al pedido

Implementación en orden

Otra variante de preorden

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

procedimiento bubbleUp(array, i, leaf) k ← 1 i ← (i - 1)/2 mientras (hoja + 1) % (k * 2) ≠ k i ← (i - 1)/2 k ← 2 * k regreso i procedimiento preordenar(matriz) yo ← 0 mientras i ≠ array.size visita(array[i]) si i = tamaño - 1 yo ← tamaño de lo contrario, si i < tamaño/2 i ← i * 2 + 1 demás hoja ← i - tamaño/2 padre ← burbuja_hacia_array, i, hoja) i ← padre * 2 + 2

Avanzar al nodo siguiente o anterior

El nodeelemento inicial puede haberse 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 a padres, es decir, utiliza un stackpara almacenar los punteros a los ancestros.

procedimiento de búsqueda(bst, clave) // devuelve un (nodo, pila) nodo ← bst.root pila ← pila vacía mientras nodo ≠ nulo pila.push(nodo) Si key = node.key, devuelve (node, stack). Si key < node.key nodo ← nodo.izquierda demás nodo ← nodo.derecha devolver ( null , pila vacía )

La función inorderNext [ 2 ] : 60 devuelve un vecino en orden de , yanode 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 pueda recorrerse secuencialmente en orden y buscarse en la dirección dada másdir adelante.

procedimiento inorderNext(nodo, directorio, pila) nuevonodo ← nodo.hijo[dir] si newnode ≠ null hacer nodo ← nuevo nodo pila.push(nodo) nuevonodo ← nodo.hijo[1-dir] hasta que newnode = null devolver (nodo, pila) // El nodo no tiene un dir-child: Si stack.isEmpty() devuelve ( null , pila vacía ) oldnode ← nodo nodo ← stack.pop() // padre de oldnode hasta que oldnode ≠ node.child[dir] // ahora oldnode = node.child[1-dir], // es decir, el nodo es el ancestro (y predecesor/sucesor) del nodo original. devolver (nodo, pila)

Nótese que la función no utiliza claves, lo que significa que la estructura secuencial se registra completamente mediante las aristas del árbol de búsqueda binaria. Para recorridos sin cambio de dirección, la complejidad promedio ( amortizada ) esO(1),{\displaystyle {\mathcal {O}}(1),}porque un recorrido completo lleva2norte−2{\displaystyle 2n-2}pasos para un BST de tamañonorte,{\displaystyle n,}1 paso para el borde hacia arriba y 1 para el borde hacia abajo. La complejidad en el peor de los casos esO(h){\displaystyle {\mathcal {O}}(h)}conh{\displaystyle h}como la altura del árbol.

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

Recorrido en orden de Morris usando enhebrado

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

Ventajas:

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

Desventajas:

  1. El árbol es más complejo.
  2. Solo podemos realizar un recorrido a la vez.
  3. Es más propenso a errores cuando ambos hijos no están presentes y ambos valores de los nodos apuntan a sus ancestros.

El recorrido de Morris es una implementación del recorrido en orden que utiliza hilos: [ 9 ]

  1. Crea enlaces al sucesor en orden.
  2. Imprime los datos usando estos enlaces.
  3. Revierte los cambios para restaurar el árbol original.

Búsqueda en amplitud

Además, a continuación se muestra un pseudocódigo para un recorrido por niveles simple basado en colas , que requerirá espacio proporcional al número máximo de nodos a una profundidad determinada. Esto puede llegar a ser hasta la mitad del número total de nodos. Un enfoque más eficiente en cuanto al espacio para este tipo de recorrido se puede implementar utilizando una búsqueda en profundidad iterativa .

procedimiento levelorder(nodo) cola ← cola vacía cola.encolar(nodo) mientras no esté vacía la cola() nodo ← cola.desencolar() visitar(nodo) si node.left ≠ null cola.encola(nodo.izquierda) Si node.right ≠ null , queue.enqueue(node.right)

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

procedimiento levelorder(array) para i desde 0 hasta array.size visita(array[i])

Árboles infinitos

Si bien el recorrido se suele realizar en árboles con un número finito de nodos (y, por lo tanto, con profundidad y factor de ramificación finitos ), también puede realizarse en árboles infinitos. Esto resulta de particular interés en la programación funcional (especialmente con evaluación perezosa ), ya que las estructuras de datos infinitas a menudo se pueden definir y manipular fácilmente, aunque no se evalúen (estrictamente), puesto que esto requeriría un tiempo infinito. Algunos árboles finitos son demasiado grandes para representarlos explícitamente, como el árbol de juego del ajedrez o del Go , por lo que resulta útil analizarlos como si fueran infinitos.

Un requisito básico para el recorrido es visitar todos los nodos eventualmente. En árboles infinitos, los algoritmos simples suelen fallar en este requisito. Por ejemplo, dado un árbol binario de profundidad infinita, una búsqueda en profundidad recorrerá un lado (por convención, el izquierdo) del árbol, sin visitar el resto, y de hecho, un recorrido en orden o en postorden nunca visitará ningún nodo, ya que no ha alcanzado una hoja (y de hecho nunca lo hará). Por el contrario, un recorrido en amplitud (por niveles) recorrerá un árbol binario de profundidad infinita sin problemas, y de hecho recorrerá cualquier árbol con un factor de ramificación limitado.

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 los hijos de un nodo), pasará al siguiente (suponiendo que no sea una búsqueda en postorden, en cuyo caso nunca llegará a la raíz). En cambio, una búsqueda en amplitud nunca llegará a los nietos, ya que busca agotar primero los hijos.

Se puede dar un análisis más sofisticado del tiempo de ejecución mediante números ordinales infinitos ; por ejemplo, la búsqueda en anchura del árbol de profundidad 2 anterior tomará ω ·2 pasos: ω para el primer nivel y luego otros ω 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 mediante 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, etiquetamos 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 correspondencia biunívoca con secuencias finitas (posiblemente vacías) de números positivos, que son contables y pueden ordenarse primero por la suma de sus 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 como resultado 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 puede interpretarse como mapear el árbol binario de profundidad infinita en este árbol y luego aplicar una búsqueda en anchura: reemplazar las aristas "hacia abajo" que conectan un nodo padre con su segundo y siguientes hijos con aristas "hacia la derecha" del primer hijo al segundo hijo, del segundo hijo al tercer hijo, etc. Así, en cada paso se puede ir hacia abajo (añadir un (, 1) al final) o hacia la derecha (sumar 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 coincide con los 2 n −1 nodos en la profundidad n − 1 en el árbol binario infinito (2 corresponde a binario).

Referencias

  1. ↑ "Lección 8, Recorrido de árboles" . Consultado el 2 de mayo de 2015 .
  2. 1 2 Pfaff, Ben (2004). Una introducción a los árboles de búsqueda binaria y los árboles equilibrados . Free Software Foundation, Inc.
  3. ↑ Métodos de recorrido de árboles binarios
  4. ↑ "Algoritmo de recorrido en preorden" . Consultado el 2 de mayo de 2015 .
  5. ↑ L antes de R significa el recorrido estándar en sentido antihorario, como se muestra en la figura.La ejecución de N antes, entre o después de L y R determina uno de los métodos descritos.Si el recorrido se realiza en sentido contrario (horario), se denomina recorrido inverso. Esto se describe en particular para el recorrido inverso en orden , cuando los datos se recuperan en orden descendente.
  6. ↑ "Algoritmos, ¿Qué combinaciones de secuenciación preorden, postorden e inorden son únicas?, Computer Science Stack Exchange" . Consultado el 2 de mayo de 2015 .
  7. ↑ Wittman, Todd. "Recorrido de árboles" (PDF) . UCLA Math . Archivado del original (PDF) el 13 de febrero de 2015. Recuperado el 2 de enero de 2016 .
  8. ↑ "estructuras de árbol constexpr" . Blog de Fekir . 9 de agosto de 2021. Consultado el 15 de agosto de 2021 .
  9. ↑ Morris, Joseph M. (1979). "Recorriendo árboles binarios de forma sencilla y económica". Information Processing Letters . 9 (5): 197– 200. doi : 10.1016/0020-0190(79)90068-1 .

Fuentes

  • Dale, Nell. Lilly, Susan D. "Estructuras de datos Pascal Plus". 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.
  • "Transversal de árbol" (math.northwestern.edu)
Obtenido de " https://en.wikipedia.org/w/index.php?title=Tree_traversal&oldid=1361728481 "
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Recorrido de gráficosEn informática , el recorrido de un grafo (también conocido como búsqueda de grafos ) se refiere al proceso de visitar (verificar y/o actualizar) c...Árbol (estructura de datos)Este árbol no ordenado tiene valores no únicos (por ejemplo, el valor 2 existe en diferentes nodos, no en un solo nodo) y no es binario (solo hasta...Un árbol binario etiquetado de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 1. El árbol anterior no está equilibrado y no está ordenado.Árbol binarioEn informática , un árbol binario es una estructura de datos en forma de árbol en la que cada nodo tiene como máximo dos hijos , denominados hijo i...Lista enlazadaLista enlazadaEn informática , una lista enlazada es una colección lineal de elementos de datos cuyo orden no está determinado por su ubicación física en la memo...Matriz (estructura de datos)Matriz (estructura de datos)En informática , una matriz es una estructura de datos que consiste en una colección de elementos ( valores o variables ), del mismo tamaño de memo...