El recorrido de árbol (también conocido como búsqueda de árbol ) es un tipo de recorrido de gráfico que provoca el proceso de visitar (comprobar y/o actualizar) cada nodo de la estructura del árbol de datos exactamente una vez. Dichos recorridos se clasifican por el orden en que se visitan los nodos. Los algoritmos del artículo se refieren a árboles binarios , pero se pueden generalizar a otros árboles.
A diferencia de las listas vinculadas , los arreglos unidimensionales y otras estructuras de datos lineales , que se recorren canónicamente en orden lineal, los árboles se pueden recorrer de varias maneras. Los árboles se pueden pasar por alto "en profundidad" o "en ancho". Hay tres formas principales de eludir "en profundidad"
Atravesar el árbol iterativamente pasa por todos los nodos de acuerdo con algún algoritmo. Dado que hay más de un nodo siguiente a un nodo dado (esta no es una estructura de datos lineal), entonces, suponiendo cálculos secuenciales (en lugar de paralelos), algunos nodos deben posponerse, es decir, almacenarse de alguna manera para una visita posterior. Esto a menudo se hace con una pila (LIFO = último en entrar, primero en salir) o una cola (FIFO = primero en entrar, primero en salir). Dado que un árbol es una estructura de datos autorreferencial (autorreferencial, definida recursivamente), 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 pendientes se almacenan explícitamente en la pila normal , implícitamente en la pila de llamadas o explícitamente en la cola .
La búsqueda primero en profundidad se implementa fácilmente a través de una pila, incluida la implementación a través de recursividad (pila de llamadas), mientras que la búsqueda primero en amplitud se implementa fácilmente a través de una cola, incluida la implementación a través de correcursión.
Estas búsquedas se denominan búsquedas en profundidad porque el árbol de búsqueda se recorre lo más abajo posible en cada descendiente antes de pasar al siguiente hermano. Para un árbol binario, se definen como operaciones para procesar un vértice recursivamente en cada nodo, comenzando desde la raíz. El algoritmo de derivación es el siguiente [2] [3]
Enfoque recursivo básico para atravesar un árbol binario (no vacío): comenzando en el nodo N, haga lo siguiente:
(L) Atraviesa el subárbol izquierdo recursivamente. Este paso termina cuando vuelve a tocar el nodo N.
(R) Atraviese el subárbol derecho recursivamente. Este paso termina cuando vuelve a tocar el nodo N.
(N) Procesar el propio nodo N.
Estos pasos se pueden realizar en cualquier orden . Si (L) ocurre antes que (R), el proceso se denomina recorrido de izquierda a derecha; de lo contrario, recorrido de derecha a izquierda. Los siguientes métodos muestran recorridos de izquierda a derecha:
Bypass directo (NLR)
En un árbol de búsqueda binaria, el recorrido centrado recupera los datos ordenados. [4] .
La secuencia transversal se llama secuenciación de árboles. La secuencia transversal es una lista de todos los nodos visitados. Ninguna de las secuenciaciones hacia adelante, hacia atrás o centradas describe de forma única un árbol. Dado un árbol con elementos distintos, un recorrido hacia adelante o hacia atrás junto con un recorrido centrado son suficientes para describir el árbol de manera única. Sin embargo, el recorrido directo junto con el recorrido inverso deja cierta ambigüedad en la estructura del árbol [5] .
Árbol de vista generalPara recorrer cualquier árbol mediante la búsqueda primero en profundidad, se realizan las siguientes operaciones recursivamente para cada nodo:
Dependiendo de la tarea actual, las operaciones transversales hacia adelante, hacia atrás o centradas pueden estar vacías, o es posible que solo desee visitar a un niño en particular, por lo que estas operaciones son opcionales. En la práctica, puede ser necesaria más de una operación transversal hacia adelante, hacia atrás o centrada. Por ejemplo, cuando se inserta en un árbol ternario, la operación transversal hacia adelante se realiza comparando los elementos. Después de esto, puede ser necesaria una operación de retroceso para equilibrar el árbol.
Los árboles también se pueden recorrer en orden de nivel , donde visitamos cada nodo en un nivel antes de pasar al siguiente nivel. Tal búsqueda se llama búsqueda primero en amplitud (BFS).
También hay algoritmos transversales que no están clasificados como búsqueda primero en profundidad o búsqueda primero en amplitud. Uno de estos algoritmos es el método Monte Carlo , que se centra en el análisis de los movimientos más prometedores en función de la expansión del árbol de búsqueda mientras se elige aleatoriamente el espacio de búsqueda.
El recorrido hacia adelante al duplicar nodos y bordes puede hacer una duplicación completa de un árbol binario . Esto se puede usar para crear una expresión de prefijo ( notación polaca ) a partir de los árboles de expresión , para lo cual iteramos la expresión en orden directo.
El recorrido centrado se usa más comúnmente en árboles de búsqueda binarios porque devuelve valores del conjunto subyacente en el orden determinado por la función de comparación que define el árbol de búsqueda binario.
El recorrido inverso al eliminar o liberar nodos puede eliminar o liberar todo el árbol binario. El recorrido también genera una representación de postfijo del árbol binario.
| preordenar (nodo) si (nodo = nulo ) volver visita (nodo) preorder(nodo.izquierda) preorder(nodo a la derecha) | iterativePreorder (nodo) si (nodo = nulo ) devuelve s ← pila vacía s.push(nodo) while ( no s.isEmpty()) nodo ← s.pop() visita (nodo) //el hijo derecho se empuja primero, por lo que el hijo izquierdo se procesa primero si (nodo.derecho ≠ nulo ) s.push(nodo.derecho) si (nodo.izquierda ≠ nulo ) s.push(nodo.izquierda) |
| inorder (nodo) if (nodo= null ) return en orden (nodo.izquierda) visita (nodo) en orden (nodo a la derecha) | iterativeInorder (nodo) s ← pila vacía mientras ( no s.isEmpty() o nodo ≠ nulo ) si (nodo ≠ nulo ) s.push(nodo) nodo ← nodo.izquierda más nodo ← s.pop() visita (nodo) nodo ← nodo.derecho |
| postorder (nodo) if (nodo= null ) return orden posterior (nodo.izquierda) postorden(nodo derecho) visita (nodo) | iterativePostorder (nodo) s ← pila vacía lastNodeVisited ← null while ( no s.isEmpty() o node ≠ null ) if (node ≠ null ) s.push(nodo) nodo ← nodo.izquierda más PeekNode ← en Peek() // si el hijo derecho existe y el recorrido provino del hijo izquierdo, muévete a la derecha if (peekNode.right ≠ null y lastNodeVisited ≠ peekNode.right) nodo ← peekNode.right más visita(peekNode) último nodo visitado ← s.pop() |
Todas las implementaciones anteriores requieren una pila proporcional a la altura del árbol, que es la pila de llamadas para la implementación recursiva y la pila principal para la iterativa. En un árbol mal balanceado, esta pila puede ser significativa. En una implementación iterativa, podemos deshacernos de la pila almacenando cada nodo en su padre o usando la unión de árboles (siguiente sección).
Bypass de Morris centrado en el firmwareEl árbol binario se une dando a cada puntero secundario izquierdo (que de lo contrario siempre está vacío = nulo) un puntero al predecesor del nodo en orden centrado (si existe), y cada puntero secundario derecho (que de lo contrario siempre está vacío) un puntero a el siguiente nodo en el orden centrado orden centrado (si existe).
ventajas:
Defectos:
Morris walk es una implementación de centered walk usando firmware [6] :
A continuación se muestra el pseudocódigo para un recorrido simple basado en cola , capa por capa. El algoritmo requiere un espacio proporcional al número máximo de nodos en los niveles. Este valor puede alcanzar la mitad de todos los nodos. Se puede implementar un enfoque más eficiente en la memoria para este tipo de recorrido utilizando la búsqueda en profundidad primero con profundización iterativa .
nivel de orden (raíz) q ← cola vacía q.encolar(raíz) while ( no q.isEmpty()) nodo ← q.dequeue() visita (nodo) si (nodo.izquierda ≠ nulo ) q.encolar(nodo.izquierda) si (nodo.derecho ≠ nulo ) q.encolar(nodo.derecha)El recorrido generalmente se realiza para árboles con un número finito de nodos (por lo tanto, profundidad finita y factor de ramificación finito ), pero también se puede realizar para árboles infinitos. Tal recorrido es de interés en particular en la programación funcional (para la evaluación perezosa ), ya que las estructuras de datos infinitas a menudo se pueden definir y manipular fácilmente, aunque no se pueden calcular (rigurosamente), ya que llevaría un tiempo infinito. Algunos árboles finitos son demasiado grandes para representarlos explícitamente, como el árbol del juego ajedrez o del go , por lo que tiene sentido tratarlos como infinitos.
El requisito principal del recorrido es visitar todos los nodos. Para árboles infinitos, los algoritmos simples no pueden hacer esto. Por ejemplo, si hay un árbol binario de profundidad infinita, la búsqueda primero en profundidad se moverá a lo largo de un lado (generalmente el lado izquierdo) del árbol, nunca visitando el resto de los vértices y, además, un recorrido centrado o hacia atrás nunca lo hará. visita cualquier nodo, ya que nunca llega a la hoja. Por el contrario, el recorrido primero en anchura (nivel por nivel) atraviesa un árbol binario de profundidad infinita sin problemas y, además, atraviesa cualquier árbol con un factor de ramificación limitado.
Por otro lado, dado un árbol de profundidad 2 en el que la raíz tiene un número infinito de hijos, y cada nodo hijo tiene dos hijos, la búsqueda en profundidad primero visitará todos los nodos, ya que, sin pasar por los nietos (hijos del segundo nivel), se mueve al siguiente nodo (suponiendo que no se trata de un recorrido hacia atrás que nunca llega a la raíz). Por el contrario, la búsqueda primero en amplitud nunca llegará a los nietos, porque tiene que iterar sobre todos los hijos (primer nivel) primero.
Se puede dar un análisis más sofisticado del tiempo de ejecución utilizando números ordinales infinitos . Por ejemplo, una búsqueda primero en anchura en un árbol de profundidad 2 (como arriba) tomará ω ·2 pasos - ω para el primer nivel y otro ω para el segundo nivel.
Por lo tanto, las búsquedas simples primero en profundidad y primero en amplitud no atraviesan ningún árbol infinito y son ineficientes en árboles muy grandes. Sin embargo, los métodos híbridos pueden atravesar cualquier árbol infinito (contable), principalmente a través del argumento diagonal ("diagonal", una combinación de vertical y horizontal, corresponde a una combinación de búsqueda primero en profundidad y búsqueda primero en amplitud).
Específicamente, dado un árbol infinitamente ramificado de profundidad infinita, llamamos a la raíz (), hijos de la raíz (1), (2), ..., nietos (1, 1), (1, 2), ... , (2, 1), (2 , 2), …, y así sucesivamente. Los nodos están entonces en correspondencia biunívoca con secuencias finitas (posiblemente vacías) de números positivos, cuyo conjunto es contable y puede ordenarse primero por la suma de elementos, y luego por orden lexicográfico dentro de secuencias con una suma dada. (solo un número finito de secuencias da una suma dada, de modo que se alcanzan todos los nodos; formalmente hablando, hay un número finito de composiciones de un número natural dado, a saber, 2 n − 1 composiciones). Este orden define el recorrido del árbol. Específicamente:
0: () once) 2: (1, 1) (2) 3: (1, 1, 1) (1, 2) (2, 1) (3) 4: (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 la asignación de un árbol binario infinitamente profundo a este tipo de árbol y la aplicación de una búsqueda en amplitud: reemplace los bordes "hacia abajo" que conectan el nodo principal con el segundo y más hijos, con los bordes "derechos" del primero. niño al segundo, del segundo al tercero y así sucesivamente. Luego, en cada paso, nos movemos hacia abajo (agregamos (, 1) hasta el final) o vamos a la derecha (agregamos uno al último número) (excepto la raíz, desde el que solo se puede bajar), que muestra la relación entre el árbol binario infinito y la numeración anterior. La suma de las entradas (sin una) corresponde a la distancia desde la raíz, que es consistente con 2 n − 1 nodos y profundidad n − 1 en un árbol binario infinito (2 corresponde al árbol binario).
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |