version itérative de l'algorithme récursif pour créer un arbre binaire

Question

Étant donné cet algorithme, j'aimerais savoir s'il existe une version itérative. De plus, je veux savoir si la version itérative peut être plus rapide.

Cette sorte de pseudo-python ...

l'algorithme renvoie une référence à la racine de l'arbre

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

Une fonction récursive avec un seul appel récursif peut généralement être transformée en une fonction récursive sans trop d'effort. Il est alors facile de la convertir en une fonction itérative. L’exemple canonique est ici factoriel:

# 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

Cependant, votre cas ici implique deux appels récursifs et, sauf si vous retravaillez considérablement votre algorithme, vous devez conserver une pile. Gérer votre propre pile peut être un peu plus rapide que d'utiliser la pile d'appels de fonctions de Python, mais la vitesse et la profondeur ajoutées ne vont probablement pas valoir la complexité. L’exemple canonique serait la séquence 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

Maintenant, votre cas est beaucoup plus compliqué que cela: un simple accumulateur aura des difficultés à exprimer un arbre partiellement construit avec un pointeur sur lequel un sous-arbre doit être généré. Vous voudrez un fermeture à glissière - difficile à mettre en œuvre dans un langage peu fonctionnel, comme Python.

Answer 2

Créer une version itérative consiste simplement à utiliser votre propre pile au lieu de la pile d’appels de langue normale. Je doute que la version itérative soit plus rapide, car la pile d'appels normale est optimisée à cet effet.

Answer 3

Les données que vous obtenez sont aléatoires. Par conséquent, l’arborescence peut être une arborescence binaire arbitraire. Dans ce cas, vous pouvez utiliser un arbre binaire threadé, qui peut être parcouru et construit sans récursivité et sans pile. Les nœuds ont un drapeau qui indique si le lien est un lien vers un autre nœud ou comment se rendre au "prochain nœud".

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

Answer 4

En fonction de la définition de "itérative", il existe une autre solution non mentionnée dans les réponses précédentes. Si "itératif" signifie simplement "non soumis à une exception de débordement de pile". (mais "autorisé à utiliser 'let rec'"), puis dans un langage prenant en charge les appels de queue, vous pouvez écrire une version en utilisant des continuations (plutôt qu'une "pile explicite"). Le code F # ci-dessous illustre cela. Il est similaire à votre problème d'origine, en ce sens qu'il génère un fichier BST à partir d'un tableau. Si le tableau est mélangé de manière aléatoire, l'arbre est relativement équilibré et la version récursive ne crée pas une pile trop profonde. Mais désactivez le brassage, l’arbre est déséquilibré et la version récursive déborde de pile alors que la version itérative avec suites se poursuit joyeusement.

#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

Oui, il est possible de rendre tout algorithme récursif itératif. Implicitement, lorsque vous créez un algorithme récursif, chaque appel place l'appel précédent sur la pile. Ce que vous voulez faire, c'est transformer la pile d'appels implicites en une pile explicite. La version itérative ne sera pas nécessairement plus rapide, mais vous n'aurez pas à craindre un débordement de pile. (est-ce que je reçois un badge pour utiliser le nom du site dans ma réponse?

Answer 6

S'il est vrai au sens général que la conversion directe d'un algorithme récursif en un algorithme itératif nécessitera une pile explicite, il existe un sous-ensemble spécifique d'algorithmes qui sont rendus directement sous forme itérative (sans avoir besoin d'une pile). . Ces rendus peuvent ne pas avoir les mêmes garanties de performance (itération sur une liste fonctionnelle vs déconstruction récursive), mais ils existent souvent.

Answer 7

Voici une solution itérative basée sur la pile (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;  
}