Как управлять деревьями в 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.

например. добавление 2 листов

Answer 1

Во-первых, вам понадобится вспомогательная функция, чтобы выяснить, какая сторона дерева «опустошена».

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

Тогда, это просто вопрос добавления 2 листьев в то время на пустее стороне (то есть, добавьте 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

ленивее подход также не должен держать обход дерева для квадратичного времени (по-прежнему принимает неоптимальный O (N * Log (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 

Edit: «это дерево уже выродились - мы должны не вырождаться его.» < - Фактически это сменяет более простое решение для бюджетирования:

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