Versão iterativa do algoritmo recursivo para fazer uma árvore binária

Question

Dado este algoritmo, gostaria de saber se existe uma versão interativa. Além disso, eu quero saber se a versão iterativa pode ser mais rápido.

Este algum tipo de pseudo-python ...

o algoritmo retorna uma referência a raiz da árvore

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

A função recursiva com apenas uma chamada recursiva geralmente pode ser transformado em uma função cauda-recursivo sem muito esforço, e, em seguida, é trivial para convertê-lo em uma função iterativa. O exemplo canônico aqui é 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

No entanto, o seu caso aqui envolve duas chamadas recursivas, ea menos que você retrabalho significativamente o seu algoritmo, você precisa manter uma pilha. Gerenciando sua própria pilha pode ser um pouco mais rápido do que usando pilha de chamadas função do Python, mas a velocidade acrescentado e profundidade, provavelmente, não vai valer a pena a complexidade. O exemplo canônico aqui seria a seqüência 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

Agora, seu caso é muito mais difícil do que isso: um acumulador simples terá dificuldades expressando uma árvore parcialmente construído com um ponteiro para onde uma subárvore precisa ser gerado. Você vai querer um zipper - não é fácil de implementar em uma linguagem não-realmente-funcional como Python.

Answer 2

Fazer uma versão iterativa é simplesmente uma questão de usar a sua própria pilha em vez da pilha normal, chamada linguagem. Eu duvido que a versão iterativa seria mais rápido, como a pilha de chamadas normal é otimizado para esta finalidade.

Answer 3

Os dados que você está recebendo é aleatória, a árvore pode ser uma árvore binária arbitrária. Para este caso, você pode usar uma árvore binária com costura, o que pode ser percorrido e construída w / o recursão e sem pilha. Os nós têm uma bandeira que indica se o link é um link para outro nó ou como chegar ao "próximo nó".

A partir http://en.wikipedia.org/wiki/Threaded_binary_tree

Answer 4

Dependendo de como você define "iterativo", não há outra solução não mencionados pelas respostas anteriores. Se "iterativo" significa apenas "não sujeitos a uma exceção de estouro de pilha" (mas "permissão para uso 'vamos rec'"), em seguida, em uma linguagem que as chamadas suportes da cauda, ??você pode escrever uma versão usando continuações (em vez de um "explícito pilha"). O # código F abaixo ilustra isso. É semelhante ao seu problema original, na medida em que constrói uma BST fora de uma matriz. Se a matriz é embaralhadas aleatoriamente, a árvore é relativamente equilibrada ea versão recursiva não cria muito profundo uma pilha. Mas desligar baralhar, e a árvore fica desequilibrada, e a versão recursiva pilha-transborda enquanto a versão iterativa-com-continuações continua ao longo feliz.

#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

Sim, é possível fazer qualquer algoritmo recursivo iterativo. Implicitamente, quando você cria um algoritmo recursivo cada chamada coloca a chamada antes para a pilha. O que você quer fazer é fazer a pilha de chamadas implícita em uma explícita. A versão iterativa não será necessariamente mais rápido, mas você não terá que se preocupar com um estouro de pilha. (Faço para obter um crachá para usar o nome do site na minha resposta?

Answer 6

Embora seja verdade no sentido geral que converter diretamente um algoritmo recursivo em um um iterativo vai exigir uma pilha explícita, há uma específica sub-conjunto de algoritmos que tornam directamente em forma iterativa (sem a necessidade de uma pilha) . Estas representações podem não ter as mesmas garantias de desempenho (iteração sobre uma lista funcional vs desconstrução recursiva), mas eles muitas vezes existe.

Answer 7

solução iterativa Aqui é baseado em pilha (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;  
}