نسخة تكرارية من خوارزمية العودية لجعل شجرة ثنائية

Question

ونظرا لهذا الخوارزمية، وأود أن أعرف إذا كان هناك وجود نسخة تكرارية. أيضا، أريد أن أعرف إذا كان إصدار متكررة يمكن أن يكون أسرع.

وهذا نوع من شبه الثعبان ...

وخوارزمية بإرجاع مرجع إلى جذر الشجرة

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

وثمة وظيفة متكررة مع دعوة متكررة واحد فقط وعادة ما يمكن أن يتحول إلى وظيفة الذيل متكررة دون الكثير من الجهد، وبعد ذلك انها تافهة لتحويله إلى وظيفة متكررة. على سبيل المثال الكنسي هنا هو مضروب:

# 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

ولكن، قضيتك هنا ينطوي على مكالمتين متكررة، وإلا إذا كنت إعادة صياغة بشكل كبير الخوارزمية الخاصة بك، تحتاج إلى الحفاظ على كومة. إدارة كومة الخاص بك قد يكون أسرع قليلا من استخدام كومة استدعاء دالة بايثون، ولكن سرعة المضافة وعمق ربما لا يكون يستحق كل هذا التعقيد. على سبيل المثال الكنسي هنا ستكون متتالية فيبوناتشي:

# 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

والآن، قضيتك أكثر صرامة بكثير من هذا: فإن تراكم بسيط صعوبات التعبير عن شجرة بنيت جزئيا مع مؤشر إلى حيث يحتاج إلى الشجرة ليتم إنشاؤه. سترغب في سحاب - ليس من السهل لتنفيذ بلغة يست حقا وظيفية مثل بيثون.

Answer 2

وإجراء النسخة التكرارية هو مجرد مسألة استخدام كومة الخاص بك بدلا من مكدس الاستدعاءات اللغة العادية. أشك في النسخة التكرارية يكون أسرع، كما هو الأمثل مكدس الاستدعاءات العادية لهذا الغرض.

Answer 3

والبيانات التي تحصل عشوائي حتى الشجرة يمكن أن تكون شجرة ثنائية تعسفية. لهذه الحالة، يمكنك استخدام شجرة ثنائية مترابطة، والتي يمكن اجتيازه وبنى ث / س عودية ولا المكدس. العقد لديها العلم أن بيان ما إذا كان الارتباط هو ارتباط إلى عقدة أخرى أو كيفية الحصول على "عقدة المقبلة".

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

Answer 4

واعتمادا على كيفية تعريف "التكرارية"، لا يوجد حل آخر غير مذكور من قبل الأجوبة السابقة. إذا كان "متكررة" تعني فقط "لا تخضع لاستثناء تجاوز سعة مكدس" (ولكن "يسمح لهم باستخدام" السماح تفصيل ")، ثم في اللغة التي تدعم المكالمات الذيل، يمكنك إرسال نسخة باستخدام استمرارا (بدلا من" صريح كومة"). يوضح # رمز F دون هذا. وهو مشابه إلى المشكلة الأصلية الخاصة بك، لأنه يبني BST من صفيف. إذا تم تعديلا مجموعة عشوائيا، وشجرة متوازنة نسبيا ولا خلق نسخة العودية عميق جدا كومة. ولكن إيقاف خلط، وكانت الشجرة يحصل غير متوازن، والنسخة عودي المكدس تجاوزات في حين أن متكررة مع-استمرارا نسخة يستمر على طول لحسن الحظ.

#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

ونعم فمن الممكن أن تجعل أي خوارزمية العودية متكررة. ضمنا، عند إنشاء خوارزمية العودية كل مكالمة تضع الدعوة السابقة إلى المكدس. ما تريد القيام به هو جعل مكدس الاستدعاءات الضمني إلى واحد واضح. والنسخة التكرارية لا تكون بالضرورة أسرع، ولكن لن يكون لديك ما يدعو للقلق تجاوز سعة مكدس. (يمكنني الحصول على شارة لاستخدام اسم الموقع في جوابي؟

Answer 6

ولئن كان صحيحا بالمعنى العام أن تحويل مباشرة خوارزمية العودية إلى واحدة متكررة سوف تحتاج إلى كومة صريح، هناك مجموعة فرعية محددة من الخوارزميات التي تجعل مباشرة في شكل متكرر (دون الحاجة إلى كومة) . هذه الاداءات قد لا يكون بنفس الضمانات الأداء (بالتكرار عبر قائمة وظيفية مقابل تفكيك عودي)، لكنهم في كثير من الأحيان وجود لها.

Answer 7

حل تكرارية

وهنا يقوم كومة (جافا):

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;  
}