Xây dựng cây nhị phân cân bằng với foldr

Question

Tôi viết hàm foldTree để xây dựng cây nhị phân cân bằng từ danh sách. Tôi phải sử dụng foldr và không sao, tôi đã sử dụng nó, nhưng tôi thực hiện insertInTree chức năng đệ quy = (hiện tại tôi chỉ biết cách này để đi qua cây =)).

CẬP NHẬT: iam không chắc về chức năng insertTree: có đúng tính toán chiều cao trong đệ quy không? = ((Cần một số trợ giúp ở đây

Có thể viết insertInTree mà không đệ quy (cái gì đó với until/iterate/unfoldr) hoặc làm foldTree chức năng mà không cần chức năng helper => ngắn hơn bằng cách nào đó

đây là thử của tôi dưới đây:.?

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 

đầu ra:

*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

chức năng chèn của bạn là do lỗi khi chiều cao hai cây con là equ al, bởi vì chèn vào đúng cây con sẽ tăng chiều cao của nó nếu nó đã đầy. Nó không phải là ngay lập tức rõ ràng với tôi cho dù tình hình như vậy sẽ bao giờ phát sinh hay không trong mã của bạn.

Cách rõ ràng đúng để chèn một yếu tố mới vào một cái cây có vẻ là

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 

Điều này tạo ra gần như cân bằng cây (còn gọi là AVL-cây). Nhưng nó đẩy mỗi phần tử mới xuống đáy của cây.

chỉnh sửa: Những cây này có thể được nhìn thấy độc đáo với

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 

Hãy thử

putStr. showTree $ foldTree "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"

Và vâng, bạn có thể viết foldTree ngắn hơn, như

foldTree = foldr insertInTree Leaf 

Answer 2

Chỉ muốn chỉ ra rằng câu trả lời được chấp nhận là tốt nhưng sẽ không hoạt động sau khi có một chiều cao 3 cân đối cây nhị phân vì nó không xem xét thực tế rằng cây bên trái có thể có chiều cao thấp hơn bên phải sau khi chèn.

Rõ ràng, các mã có thể đã làm việc thêm một điều kiện bổ sung:

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