algorithm - avl - Árbol iterativo caminando

tree structure architecture

Question

Ha pasado bastante tiempo desde que tomé estructuras de datos y algoritmos en la universidad, así que recientemente me sorprendió la sugerencia de que la recursión puede no ser la forma (tm) de cruzar los árboles. Por alguna razón iterativa, el recorrido basado en la cola no ha sido una técnica que haya usado alguna vez.

¿Cuáles son, si las hay, las ventajas del recorrido iterativo frente al recursivo? ¿En qué situaciones podría usar uno en lugar de otro?

Answer 1

Depende de si desea realizar el recorrido de profundidad primero o ancho de primer recorrido. La primera profundidad es la más fácil de implementar a través de la recursión. Con Breadth-first necesita mantener una cola de nodos para expandirse en el futuro.

Answer 2

En realidad, debería usar la cola para la primera búsqueda de amplitud y apilar para la primera búsqueda de profundidad, y ejecutar su algoritmo desde un ciclo while. Hacer llamadas de funciones recursivas puede arrastrar su programa de manera significativa si realiza operaciones simples durante el desplazamiento, y puede causar un desbordamiento de la pila, pero en estos días tendría que esforzarse mucho para ver una.

Simplemente tenga un hash al lado para realizar un seguimiento de los nodos ya visitados en caso de que no sea un árbol sino un gráfico bien conectado.

Answer 3

Si tiene una cantidad fija de memoria dedicada a la pila, como suele hacer (esto es especialmente un problema en muchas configuraciones Java JVM), la recursión puede no funcionar bien si tiene un árbol profundo (o si la profundidad de recursión es alta en cualquier otro escenario); causará un desbordamiento de la pila. Un enfoque iterativo, empujar nodos para visitar en una cola (para BFS-like transversal) o stack (para DFS-like transversal) tiene mejores propiedades de memoria de varias maneras, por lo que si esto importa, utilice un enfoque iterativo.

La ventaja de la recursión es la simplicidad / elegancia de la expresión, no el rendimiento. Recordar que esa es la clave para elegir el enfoque apropiado para un algoritmo, tamaño de problema y arquitectura de máquina dados.

Answer 4

Si está haciendo una primera búsqueda de amplitud, la implementación natural es insertar nodos en una cola, no utilizar la recursión.

Si está haciendo una primera búsqueda en profundidad, la recursión es la forma más natural de codificar el recorrido. Sin embargo, a menos que su compilador optimice la repetición de cola en iteración, su implementación recursiva será más lenta que un algoritmo iterativo, y morirá con un desbordamiento de pila en un árbol lo suficientemente profundo.

Algunos rápidos Python para ilustrar la diferencia:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))
def bfs(t):
    to_visit = [t]
    while len(to_visit) > 0:
        c = to_visit[0]
        if type(c) is int:
            print c
        else: 
            print c[0]
            to_visit.append(c[1])
            if len(c) > 2: to_visit.append(c[2])
        to_visit = to_visit[1:]

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

bfs(t)
dfs(t)

Answer 5

Vaya con recursivo, porque en realidad podría obtener un error de desbordamiento de pila, y esto es .com, después de todo.