iterative Version des rekursiven Algorithmus einen binären Baum zu machen

StackOverflow https://stackoverflow.com/questions/235868

Frage

Mit diesem Algorithmus gegeben, ich möchte wissen, ob es eine iterative Version existiert. Auch ich möchte wissen, ob die iterative Version schneller sein kann.

Dieses eine Art Pseudo-Python ...

der Algorithmus gibt eine Referenz auf Wurzel des Baumes 

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
War es hilfreich?

Lösung

Eine rekursive Funktion mit nur einem rekursiven Aufruf kann in der Regel in einen Schwanz-rekursive Funktion, ohne zu viel Aufwand gedreht werden, und es ist dann trivial es in eine iterative Funktion zu konvertieren. Das bekannteste Beispiel ist hier faktorielles: 

# 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

Allerdings Ihr Fall hier beinhaltet zwei rekursive Aufrufe, und es sei denn, Sie deutlich Ihren Algorithmus überarbeiten, müssen Sie einen Stapel halten. Ihre eigenen Stapel verwalten kann ein wenig schneller als die Verwendung von Python-Funktion Call-Stack, aber die zusätzliche Geschwindigkeit und Tiefe werden wahrscheinlich nicht die Komplexität wert sein. Das bekannteste Beispiel wäre hier die Fibonacci-Folge sein: 

# 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

Nun, den Fall ist viel härter als das: ein einfacher Akkumulator wird Schwierigkeiten haben, einen teilweise gebauten Baum mit einem Zeiger zum Ausdruck zu bringen, wo eine Teilstruktur erzeugt werden muss. Hier finden Sie eine Reißverschluss wollen - nicht einfach in einem nicht-wirklich-funktionale Sprache zu implementieren wie Python.

Andere Tipps

eine iterative Version zu machen ist einfach eine Frage des eigenen Stapel anstelle der normalen Sprache Call-Stack verwenden. Ich bezweifle, dass die iterative Version schneller wäre, als das normale Call-Stack für diesen Zweck optimiert ist.

Die Daten, die Sie bekommen sind zufällig so der Baum ein beliebiger binärer Baum sein kann. Für diesen Fall können Sie einen Gewinde binären Baum, verwenden Sie die und gebaut w / o Rekursion und keinen Stapel durchlaufen werden kann. Die Knoten haben einen Flag, das anzeigt, ob die Verbindung eine Verbindung zu einem anderen Knoten ist oder wie man den „nächste Knoten“ zu bekommen.

http://en.wikipedia.org/wiki/Threaded_binary_tree alt text

Je nachdem, wie Sie definieren „iterative“, gibt es eine andere Lösung nicht von den früheren Antworten erwähnt. Wenn „iterative“ bedeutet nur „nicht in eine Stapelüberlaufausnahme“ (aber „benutzen dürfen‚lassen rec‘“), dann in einer Sprache, die Endrekursion unterstützt, können Sie eine Version mit Fortsetzungen schreiben (und nicht als „explicit Stapel"). Der F # Code unten verdeutlicht dies. Es ist ähnlich wie Ihr ursprüngliches Problem, dass es ein BST aus einem Array aufbaut. Wenn das Array zufällig gemischt wird, ist der Baum relativ ausgeglichen und die rekursive Version schafft nicht zu tief einen Stapel. Aber schalten Sie schlurfen, und der Baum wird unausgewogen, und die rekursive Version Stack-Überlauf, während die iterative-mit-Fortsetzungen Version zusammen glücklich weiter. 

#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)

Ja, es ist möglich, eine beliebige rekursive Algorithmus iterativ zu machen. Implizit, wenn Sie einen rekursiven Algorithmus jeder Anruf erstellen platziert den vorherigen Aufruf auf den Stapel. Was Sie tun möchten, ist die implizite Call-Stack in eine explizite zu machen. Die iterative Version wird nicht unbedingt schneller, aber Sie werden nicht über einen Stapelüberlauf zu kümmern. (Erhalte ich ein Abzeichen für die Verwendung der Namen der Website in meiner Antwort?

Während es im allgemeinen Sinne wahr ist, die direkt einen rekursiven Algorithmus in einen iterativen eine Umwandlung wird einen expliziten Stapel erfordern, gibt es eine bestimmte Untergruppe von Algorithmen, die direkt in iterativer Form machen (ohne die Notwendigkeit für einen Stapel) . Diese Renderings können nicht die gleichen Leistungsgarantien haben (Iterieren über eine Funktionsliste vs rekursive Dekonstruktion), aber sie existieren oft.

Hier wird Stack basiert iterative Lösung (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;  
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top