Buildr ile dengeli ikili ağaç oluşturma

Question

Listeden dengeli ikili ağaç oluşturan foldTree işlevini yazarım. foldr kullanmalıyım ve sorun değil, kullandım ama insertInTree fonksiyonunu tekrarlıyorum = (şimdilik sadece ağaçların arasından yürümek için bu yolu biliyorum =)).

UPDATE: işlev hakkında emin değilim. insertTree: doğrudur. . = ((O until/iterate/unfoldr ile (bir şey) özyineleme olmadan insertInTree yazmak mümkün mü

burada yardıma ihtiyacım veya yardımcı işlevleri olmadan foldTree fonksiyonunu yapmak => daha kısa bir şekilde

bu aşağıda benim deneyin geçerli:?

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 

çıkışı:

*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

ekleme fonksiyon hatası olduğu iki alt ağaçların yükseklikleri eQU ne al, çünkü sağ alt ağacın içine sokulması zaten doluysa yüksekliğini artıracaktır. Kodunuzda böyle bir durumun ortaya çıkıp çıkmayacağı bana açık değildir.

bir ağaca yeni bir öğe eklemek için görünüşte doğru yolu Bu neredeyse dengelenmiş ağaçları (nam-ı diğer AVL ağaçlar) oluşturur

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 

gibi görünüyor. Ama her yeni öğeyi ağacın en altına iter.

düzenleme: Bu ağaçlar güzel

putStr deneyin

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 

ile görülebilir. showTree $ foldTree "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"

Ve evet, sadece kabul cevap iyi olduğunu işaret etmek istiyorum

foldTree = foldr insertInTree Leaf 

Answer 2

olarak, foldTree daha kısa yazabilir ancak 3 dengeli bir yüksekliğe yaptıktan sonra işe yaramaz İkili ağaç, sol ağacın eklendikten sonra sağdan daha az yüksekliğe sahip olabileceğini düşünmüyordu.

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