versione iterativa dell'algoritmo ricorsivo per creare un albero binario

Question

Dato questo algoritmo, vorrei sapere se esiste una versione iterativa. Inoltre, voglio sapere se la versione iterativa può essere più veloce.

Questa è una specie di pseudo-pitone ...

l'algoritmo restituisce un riferimento alla radice dell'albero

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 funzione ricorsiva con una sola chiamata ricorsiva di solito può essere trasformata in una funzione ricorsiva della coda senza troppi sforzi, e quindi è banale convertirla in una funzione iterativa. L'esempio canonico qui è fattoriale:

# 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

Tuttavia, il tuo caso qui prevede due chiamate ricorsive e, a meno che non rielabori in modo significativo l'algoritmo, devi mantenere uno stack. Gestire il proprio stack potrebbe essere un po 'più veloce rispetto all'utilizzo dello stack di chiamate delle funzioni di Python, ma la velocità e la profondità aggiunte probabilmente non valgono la complessità. L'esempio canonico qui sarebbe la sequenza di 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

Ora, il tuo caso è molto più duro di così: un semplice accumulatore avrà difficoltà ad esprimere un albero parzialmente costruito con un puntatore al punto in cui deve essere generato un sottotree. Ti consigliamo una zipper - non facile da implementare in un linguaggio non veramente funzionale come Python.

Answer 2

Creare una versione iterativa è semplicemente una questione di usare il proprio stack anziché il normale stack di chiamate in lingua. Dubito che la versione iterativa sarebbe più veloce, poiché il normale stack di chiamate è ottimizzato per questo scopo.

Answer 3

I dati che ricevi sono casuali, quindi l'albero può essere un albero binario arbitrario. In questo caso, è possibile utilizzare un albero binario filettato, che può essere attraversato e creato senza ricorsione e senza stack. I nodi hanno un flag che indica se il collegamento è un collegamento a un altro nodo o come arrivare al "nodo successivo".

Da http://en.wikipedia.org/wiki/Threaded_binary_tree

Answer 4

A seconda di come definisci " iterativo " ;, esiste un'altra soluzione non menzionata dalle risposte precedenti. Se " iterativo " significa solo "non soggetto a un'eccezione di overflow dello stack" (ma "permesso di usare" let rec "), quindi in una lingua che supporta le chiamate di coda, puoi scrivere una versione usando le continuazioni (piuttosto che uno" stack esplicito "). Il seguente codice F # illustra questo. È simile al problema originale, in quanto crea un BST da un array. Se l'array viene mischiato casualmente, l'albero è relativamente bilanciato e la versione ricorsiva non crea uno stack troppo profondo. Ma disattiva il mescolamento e l'albero viene sbilanciato e la versione ricorsiva si sovrappone allo stack, mentre la versione iterativa con continuazioni continua felicemente.

#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ì, è possibile rendere iterativo qualsiasi algoritmo ricorsivo. Implicitamente, quando si crea un algoritmo ricorsivo ogni chiamata inserisce la chiamata precedente nello stack. Quello che vuoi fare è rendere lo stack di chiamate implicito in uno esplicito. La versione iterativa non sarà necessariamente più veloce, ma non dovrai preoccuparti di un overflow dello stack. (ottengo un badge per l'utilizzo del nome del sito nella mia risposta?

Answer 6

Sebbene sia vero nel senso generale che la conversione diretta di un algoritmo ricorsivo in uno iterativo richiederà uno stack esplicito, esiste un sottoinsieme specifico di algoritmi che viene visualizzato direttamente in forma iterativa (senza la necessità di uno stack) . Questi rendering potrebbero non avere le stesse garanzie di prestazione (iterando su un elenco funzionale vs decostruzione ricorsiva), ma spesso esistono.

Answer 7

Ecco la soluzione iterativa basata su stack (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;  
}