versión iterativa del algoritmo recursivo para hacer un árbol binario

Question

Dado este algoritmo, me gustaría saber si existe una versión iterativa. Además, quiero saber si la versión iterativa puede ser más rápida.

Esto es una especie de pseudo-pitón ...

el algoritmo devuelve una referencia a la raíz del árbol

make_tree(array a)
  if len(a) == 0
        return None;

  node = pick a random point from the array
  calculate distances of the point against the others
  calculate median of such distances
  node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
  node.right = make_tree(subset, such the distance is greater or equal to the median)
  return node

Answer 1

Una función recursiva con una sola llamada recursiva generalmente se puede convertir en una función recursiva de cola sin demasiado esfuerzo, y luego es trivial convertirla en una función iterativa. El ejemplo canónico aquí es factorial:

# naïve recursion
def fac(n):
    if n <= 1:
        return 1
    else:
        return n * fac(n - 1)

# tail-recursive with accumulator
def fac(n):
    def fac_helper(m, k):
        if m <= 1:
            return k
        else:
            return fac_helper(m - 1, m * k)
    return fac_helper(n, 1)

# iterative with accumulator
def fac(n):
    k = 1
    while n > 1:
        n, k = n - 1, n * k
    return k

Sin embargo, su caso aquí implica dos llamadas recursivas y, a menos que vuelva a trabajar de manera significativa su algoritmo, debe mantener una pila. La administración de su propia pila puede ser un poco más rápida que usar la pila de llamadas de función de Python, pero la velocidad y profundidad agregadas probablemente no valdrán la pena por la complejidad. El ejemplo canónico aquí sería la secuencia de Fibonacci:

# naïve recursion
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

# tail-recursive with accumulator and stack
def fib(n):
    def fib_helper(m, k, stack):
        if m <= 1:
            if stack:
                m = stack.pop()
                return fib_helper(m, k + 1, stack)
            else:
                return k + 1
        else:
            stack.append(m - 2)
            return fib_helper(m - 1, k, stack)
    return fib_helper(n, 0, [])

# iterative with accumulator and stack
def fib(n):
    k, stack = 0, []
    while 1:
        if n <= 1:
            k = k + 1
            if stack:
                n = stack.pop()
            else:
                break
        else:
            stack.append(n - 2)
            n = n - 1
    return k

Ahora, su caso es mucho más difícil que esto: un acumulador simple tendrá dificultades para expresar un árbol parcialmente construido con un puntero a donde se necesita generar un subárbol. Querrá una cremallera , no es fácil de implementar en un lenguaje no realmente funcional como Python.

Answer 2

Hacer una versión iterativa es simplemente una cuestión de usar su propia pila en lugar de la pila normal de llamadas de idioma. Dudo que la versión iterativa sea más rápida, ya que la pila de llamadas normal está optimizada para este propósito.

Answer 3

Los datos que está obteniendo son aleatorios, por lo que el árbol puede ser un árbol binario arbitrario. Para este caso, puede usar un árbol binario con hilos, que se puede atravesar y construir sin recursión y sin pila. Los nodos tienen una marca que indica si el enlace es un enlace a otro nodo o cómo llegar al siguiente nodo " ;.

De http://en.wikipedia.org/wiki/Threaded_binary_tree ??

Answer 4

Dependiendo de cómo defina " iterativo " ;, hay otra solución que no se menciona en las respuestas anteriores. Si '' iterativo '' solo significa que " no está sujeto a una excepción de desbordamiento de pila " (pero " permite usar 'let rec' "), luego, en un lenguaje que admita llamadas de cola, puede escribir una versión usando continuaciones (en lugar de una " pila explícita "). El código F # a continuación ilustra esto. Es similar a su problema original, ya que construye un BST a partir de una matriz. Si la matriz se baraja aleatoriamente, el árbol está relativamente equilibrado y la versión recursiva no crea una pila demasiado profunda. Pero desactiva el orden aleatorio, y el árbol se desequilibra, y la versión recursiva se desborda en la pila, mientras que la versión iterativa con continuaciones continúa felizmente.

#light 
open System

let printResults = false
let MAX = 20000
let shuffleIt = true

// handy helper function
let rng = new Random(0)
let shuffle (arr : array<'a>) = // '
    let n = arr.Length
    for x in 1..n do
        let i = n-x
        let j = rng.Next(i+1)
        let tmp = arr.[i]
        arr.[i] <- arr.[j]
        arr.[j] <- tmp

// Same random array
let sampleArray = Array.init MAX (fun x -> x) 
if shuffleIt then
    shuffle sampleArray

if printResults then
    printfn "Sample array is %A" sampleArray

// Tree type
type Tree =
    | Node of int * Tree * Tree
    | Leaf

// MakeTree1 is recursive
let rec MakeTree1 (arr : array<int>) lo hi =  // [lo,hi)
    if lo = hi then
        Leaf
    else
        let pivot = arr.[lo]
        // partition
        let mutable storeIndex = lo + 1
        for i in lo + 1 .. hi - 1 do
            if arr.[i] < pivot then
                let tmp = arr.[i]
                arr.[i] <- arr.[storeIndex]
                arr.[storeIndex] <- tmp 
                storeIndex <- storeIndex + 1
        Node(pivot, MakeTree1 arr (lo+1) storeIndex, MakeTree1 arr storeIndex hi)

// MakeTree2 has all tail calls (uses continuations rather than a stack, see
// http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!171.entry 
// for more explanation)
let MakeTree2 (arr : array<int>) lo hi =  // [lo,hi)
    let rec MakeTree2Helper (arr : array<int>) lo hi k =
        if lo = hi then
            k Leaf
        else
            let pivot = arr.[lo]
            // partition
            let storeIndex = ref(lo + 1)
            for i in lo + 1 .. hi - 1 do
                if arr.[i] < pivot then
                    let tmp = arr.[i]
                    arr.[i] <- arr.[!storeIndex]
                    arr.[!storeIndex] <- tmp 
                    storeIndex := !storeIndex + 1
            MakeTree2Helper arr (lo+1) !storeIndex (fun lacc ->
                MakeTree2Helper arr !storeIndex hi (fun racc ->
                    k (Node(pivot,lacc,racc))))
    MakeTree2Helper arr lo hi (fun x -> x)

// MakeTree2 never stack overflows
printfn "calling MakeTree2..."
let tree2 = MakeTree2 sampleArray 0 MAX
if printResults then
    printfn "MakeTree2 yields"
    printfn "%A" tree2

// MakeTree1 might stack overflow
printfn "calling MakeTree1..."
let tree1 = MakeTree1 sampleArray 0 MAX
if printResults then
    printfn "MakeTree1 yields"
    printfn "%A" tree1

printfn "Trees are equal: %A" (tree1 = tree2)

Answer 5

Sí, es posible hacer que cualquier algoritmo recursivo sea iterativo. Implícitamente, cuando creas un algoritmo recursivo, cada llamada coloca la llamada anterior en la pila. Lo que desea hacer es convertir la llamada implícita en una explícita. La versión iterativa no necesariamente será más rápida, pero no tendrá que preocuparse por un desbordamiento de pila. (¿Obtengo una identificación por usar el nombre del sitio en mi respuesta?

Answer 6

Si bien es cierto en el sentido general de que convertir un algoritmo recursivo directamente en uno iterativo requerirá una pila explícita, hay un subconjunto específico de algoritmos que se procesan directamente en forma iterativa (sin la necesidad de una pila) . Es posible que estas representaciones no tengan las mismas garantías de rendimiento (iteración sobre una lista funcional frente a la deconstrucción recursiva), pero a menudo existen.

Answer 7

Aquí está la solución iterativa basada en pila (Java):

public static Tree builtBSTFromSortedArray(int[] inputArray){

    Stack toBeDone=new Stack("sub trees to be created under these nodes");

    //initialize start and end 
    int start=0;
    int end=inputArray.length-1;

    //keep memoy of the position (in the array) of the previously created node
    int previous_end=end;
    int previous_start=start;

    //Create the result tree 
    Node root=new Node(inputArray[(start+end)/2]);
    Tree result=new Tree(root);
    while(root!=null){
        System.out.println("Current root="+root.data);

        //calculate last middle (last node position using the last start and last end)
        int last_mid=(previous_start+previous_end)/2;

        //*********** add left node to the previously created node ***********
        //calculate new start and new end positions
        //end is the previous index position minus 1
        end=last_mid-1; 
        //start will not change for left nodes generation
        start=previous_start; 
        //check if the index exists in the array and add the left node
        if (end>=start){
            root.left=new Node(inputArray[((start+end)/2)]);
            System.out.println("\tCurrent root.left="+root.left.data);
        }
        else
            root.left=null;
        //save previous_end value (to be used in right node creation)
        int previous_end_bck=previous_end;
        //update previous end
        previous_end=end;

        //*********** add right node to the previously created node ***********
        //get the initial value (inside the current iteration) of previous end
        end=previous_end_bck;
        //start is the previous index position plus one
        start=last_mid+1;
        //check if the index exists in the array and add the right node
        if (start<=end){
            root.right=new Node(inputArray[((start+end)/2)]);
            System.out.println("\tCurrent root.right="+root.right.data);
            //save the created node and its index position (start & end) in the array to toBeDone stack
            toBeDone.push(root.right);
            toBeDone.push(new Node(start));
            toBeDone.push(new Node(end));   
        }

        //*********** update the value of root ***********
        if (root.left!=null){
            root=root.left; 
        }
        else{
            if (toBeDone.top!=null) previous_end=toBeDone.pop().data;
            if (toBeDone.top!=null) previous_start=toBeDone.pop().data;
            root=toBeDone.pop();    
        }
    }
    return result;  
}