foldrで平衡した二分木を構築する

Question

リストから平衡二分木を構築する関数foldTreeを書く。 私はfoldrを使用しなければなりません。それは大丈夫です、私はそれを使用しましたが、私はinsertInTree関数を再帰的にします=（今のところ私は木を通り抜けるこの方法しか知っていません））。

更新日：iamは関数についてはわかりませんinsertTree：再帰の高さを正しく計算していますか？ 。=（（それはuntil/iterate/unfoldrと（何か）は、再帰なしinsertInTreeを書き込むことができる

ここにいくつかの助けを必要とするか、ヘルパー関数なしfoldTree機能を作る=>短い何とか

これは以下の私の試みです：？

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 

出力：

*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

二つのサブ木高さがEQUされたら挿入機能にエラーがあります右側のサブツリーに挿入すると、すでにフルであればその高さが増加するためです。このような状況が発生するかどうかは、すぐには分かりません。

ツリーに新しい要素を挿入する明らかに正しい方法は、これは、ほぼ均衡木（別称、AVL木）を作成

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 

のようです。しかし、新しい要素をツリーの一番下まで押し込む。

編集：これらの木はうまく

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 

で見ることができ

putStrを試してみてください。 showTree $ foldTree「ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890」

そして、はい、あなただけ受け入れ答えが良好であることを指摘したい

foldTree = foldr insertInTree Leaf 

Answer 2

として、foldTree短く書くことができますが、3バランスの取れた高さを有する後に動作しません。バイナリツリーは、挿入後に左のツリーの高さが右のものよりも小さくなる可能性があることを考慮していないためです。

はどうやら、コードが余分な条件を追加する働いてきたことができます：

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