이진 트리를 만들기위한 재귀 알고리즘의 반복 버전
https://stackoverflow.com/questions/235868
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이 알고리즘이 주어지면 반복 버전이 있는지 알고 싶습니다. 또한 반복 버전이 더 빠를 수 있는지 알고 싶습니다.
이것은 일종의 의사-파이썬 ...
알고리즘은 트리의 루트에 대한 참조를 반환합니다.
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
해결책
하나의 재귀 호출 만 갖는 재귀 함수는 일반적으로 너무 많은 노력없이 꼬리 수반 기능으로 바뀔 수 있으며,이를 반복적 인 함수로 변환하는 것은 사소한 일입니다. 여기서 표준의 예는 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
그러나 여기의 사례에는 두 개의 재귀 통화가 포함되며 알고리즘을 크게 재 작업하지 않으면 스택을 유지해야합니다. 자신의 스택을 관리하는 것이 Python의 기능 통화 스택을 사용하는 것보다 조금 더 빠를 수 있지만 추가 된 속도와 깊이는 복잡한 가치가 없을 것입니다. 여기서 표준의 예는 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
이제 귀하의 사례는 이것보다 훨씬 힘들다. 간단한 축적기는 하위 트리를 생성 해야하는 위치에 대한 포인터가있는 부분적으로 만들어진 트리를 표현하는 데 어려움이있다. 당신은 원할 것입니다 지퍼 -Python과 같은 명백한 기능이없는 언어로 구현하기는 쉽지 않습니다.
다른 팁
반복 버전을 만드는 것은 단순히 일반 언어 통화 스택 대신 자신의 스택을 사용하는 문제입니다. 일반적인 통화 스택 이이 목적을 위해 최적화되어 있기 때문에 반복 버전이 더 빠를 것 같지는 않습니다.
당신이 얻는 데이터는 무작위이므로 트리는 임의의 이진 트리가 될 수 있습니다. 이 경우 나사산 바이너리 트리를 사용할 수 있으며,이 바이너리 트리를 사용할 수 있으며, 재귀가없고 스택이 없을 수 있습니다. 노드에는 링크가 다른 노드에 대한 링크인지 또는 "다음 노드"로 이동하는 방법을 나타내는 플래그가 있습니다.
"반복"을 정의하는 방법에 따라 이전 답변에서 언급하지 않은 다른 해결책이 있습니다. "반복"은 "스택 오버플로 예외에 적용되지 않는다"(그러나 "let rec '를 사용할 수 있도록 허용됨")를 의미하는 경우, 테일 호출을 지원하는 언어로 "명시 적이 아닌 연속성을 사용하여 버전을 쓸 수 있습니다. 스택"). 아래의 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)
예, 재귀 알고리즘 반복을 만들 수 있습니다. 암시 적으로, 재귀 알고리즘을 만들 때 각 호출은 이전 호출을 스택에 배치합니다. 당신이하고 싶은 것은 암시 적 호출을 명시 적으로 쌓는 것입니다. 반복 버전이 반드시 더 빠르지는 않지만 스택 오버플로에 대해 걱정할 필요는 없습니다. (내 답변에서 사이트 이름을 사용하기위한 배지를 얻습니까?
일반적인 의미에서 재귀 알고리즘을 반복적 인 알고리즘으로 직접 변환하려면 명시 적 스택이 필요하다는 것이 사실이지만, 스택이 필요하지 않으면 반복 형태로 직접 렌더링하는 특정 하위 세트가 있습니다. 이러한 렌더링은 동일한 성능 보장을받지 못할 수 있지만 (기능 목록과 재귀 해체를 반복) 종종 존재합니다.
스택 기반 반복 솔루션 (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;
}
