Haskell에서 나무를 조작하는 방법

Question

주어진 n이 나무를 퇴화시키지 않고 잎의 양을 정확히 더할 수있는 함수를 작성하고 싶습니다. 이런 식으로 뭔가 :

data SimpleT= L | N SimpleT SimpleT deriving Show 

및 addTree과 같이 정의 :

addTree::Int->SimpleT->SimpleT 
addTree n (N left right) = something 

그러나 나는 바로 그것을 얻을 수 없습니다. 내가 지금까지 가지고있는 유일한 작업 것은, 단지 모든 잎에 (N의 L L)를 추가합니다

는

addTree2 L = (N L L) 
addTree2 (N left right)= N (addTree2 left)(addTree2 right) 

어떻게 'n'을 적절하게 추가 할 수 있습니까? n의 짝수 만 허용됩니다.

2 개의 잎을 더하는 것

Answer 1

첫째로, 당신은 나무의 어느 쪽이 "emptier"인지 알기위한 조력자의 기능이 필요할 것이다.

height :: SimpleT -> Int 
height L = 0 
height (N l r) = 1 + max (height l) (height r) 

다음에, (즉, 다음, 텅 비어 측에 2 개 잎을 추가 결과 트리에 n-2 잎을 추가한다)이 텅 비어 옆으로 한 번에 두 잎을 추가의 문제입니다.

-- Warning: partial function, not defined for odd n 
addTree :: Int -> SimpleT -> SimpleT 
addTree 0 t = t 
addTree n L = addTree (n - 2) (N L L) 
addTree n (N l r) = addTree (n - 2) (if height l > height r 
            then (N l (addTree 2 r)) 
            else (N (addTree 2 l) r)) 

Answer 2

lazier 방법도 불구하고 차 시간 (여전히 필요 차선 O (N * 로그 (N))의 트리를 통과 유지하지 않으며, "최초의"귀하의 예제의 오른쪽 절반으로 줄 것이다 가) 텅 비어 있기 때문에 :

size :: SimpleT -> Int 
size L = 1 
size (N l r) = size l + size r 

addTree :: Int -> SimpleT -> SimpleT 
addTree 0 t = t 
addTree n L = addTree (n-1) (N L L) 
addTree n (N l r) = let (u, v) = budget (size l) (size r) n in 
    N (addTree u l) (addTree v r) 

budget :: Int -> Int -> Int -> (Int, Int) 
budget l r n = let 
    l' = min (n+l) r -- Raise l to r from our budget n 
    n' = n+l-l' 
    r' = min (n'+r) l' -- Raise r to l from our budget n 
    n'' = n'+r-r' 
    n''' = div n'' 2 
    in (l'-l+n''-n''', r'-r+n''') -- Divide our remaining budget fairly 

편집 : "그 나무는 퇴화 이미 - 우리는 그것을 퇴화하지 않도록되어 있습니다." < - 사실 더 간단한 예산 책정 솔루션을 제공합니다.

budget :: Int -> Int -> Int -> (Int, Int) 
budget l r n = let (n', m) = divMod n 2 
    in (if l>r then swap else id) (n'+m,n')