Buduj zbalansowane drzewo binarne z foldrem

Question

Piszę funkcję foldTree budującą zbalansowane drzewo binarne z listy. Muszę użyć foldr i jest ok, użyłem go, ale robię insertInTree funkcji rekursywnej = (na razie wiem tylko w ten sposób, aby przejść przez drzewa =)).

UPDATE: nie iam pewien funkcji insertTree: jest to prawo obliczyć wysokość w rekursji ?? = ((Potrzebuję pomocy tutaj

Czy to możliwe, aby napisać insertInTree bez rekursji (coś z until/iterate/unfoldr) lub dokonać foldTree funkcji bez funkcji pomocniczych => krótszy jakoś

to moja próba poniżej:.?

data Tree a = Leaf 
      | Node Integer (Tree a) a (Tree a) 
      deriving (Show, Eq) 

foldTree :: [a] -> Tree a 
foldTree = foldr (\x tree -> insertInTree x tree) Leaf 

insertInTree :: a -> Tree a -> Tree a 
insertInTree x Leaf = Node 0 (Leaf) x (Leaf) 
insertInTree x (Node n t1 val t2) = if h1 < h2 
            then Node (h2+1) (insertInTree x t1) val t2 
            else Node (h1+1) t1 val (insertInTree x t2) 
    where h1 = heightTree t1 
     h2 = heightTree t2 

heightTree :: Tree a -> Integer 
heightTree Leaf = 0 
heightTree (Node n t1 val t2) = n 

wyjściowa:

*Main> foldTree "ABCDEFGHIJ" 
Node 3 (Node 2 (Node 0 Leaf 'B' Leaf) 'G' (Node 1 Leaf 'F' (Node 0 Leaf 'C' Leaf))) 'J' (Node 2 (Node 1 Leaf 'D' (Node 0 Leaf 'A' Leaf)) 'I' (Node 1 Leaf 'H' (Node 0 Leaf 'E' Leaf))) 
*Main> 

Answer 1

Twoja funkcja wstawiania jest w błędzie, gdy wysokość obu sub-trees' są EQU al, ponieważ wstawienie do prawego pod-drzewa zwiększy jego wysokość, jeśli był już pełny. Nie jest dla mnie jasne, czy taka sytuacja kiedykolwiek wystąpi w twoim kodzie.

Pozornie prawidłowy sposób, aby wstawić nowy element w drzewo wydaje się być

insertInTree x (Node n t1 val t2) 
    | h1 < h2 = Node n (insertInTree x t1) val t2 
    | h1 > h2 = Node n t1 val t2n 
    | otherwise = Node (h+1) t1 val t2n 
    where h1 = heightTree t1 
     h2 = heightTree t2 
     t2n = insertInTree x t2 
     h = heightTree t2n  -- might stay the same 

Stwarza prawie zbilansowane Drzewa (a.k.a. AVL-drzewa). Ale przesuwa każdy nowy element na samo dno drzewa.

edit: Drzewa te mogą być ładnie widać z

showTree Leaf = "" 
showTree n@(Node i _ _ _) = go i n 
    where 
    go _ (Leaf) = "" 
    go i (Node _ l c r) = go (i-1) l ++ 
    replicate (4*fromIntegral i) ' ' ++ show C++ "\n" ++ go (i-1) r 

Spróbuj

putStr. showTree $ foldTree „ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890”

I tak, można napisać foldTree krótsze, jak

foldTree = foldr insertInTree Leaf 

Answer 2

prostu chcę podkreślić, że przyjęte rozwiązanie jest dobre, ale nie będzie działać po wysokość 3 zrównoważony drzewo binarne, ponieważ nie uwzględniało faktu, że lewe drzewo może mieć mniejszą wysokość niż prawa po wstawieniu.

Wydaje się, że kod może Pracowałam dodając dodatkowy warunek:

insertInTree x (Node n t1 val t2) 
    | h1 < h2 = Node n  t1n val t2 
    | h1 > h2 = Node n  t1 val t2n 
    | nh1 < nh2 = Node n  t1n val t2 
    | otherwise = Node (nh2+1) t1 val t2n 
    where h1 = heightTree t1 
     h2 = heightTree t2 
     t1n = insertInTree x t1 
     t2n = insertInTree x t2 
     nh1 = heightTree t1n 
     nh2 = heightTree t2n