diff options
Diffstat (limited to '54a-60/60.hs')
-rw-r--r-- | 54a-60/60.hs | 25 |
1 files changed, 25 insertions, 0 deletions
diff --git a/54a-60/60.hs b/54a-60/60.hs new file mode 100644 index 0000000..3facc1f --- /dev/null +++ b/54a-60/60.hs @@ -0,0 +1,25 @@ +data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq) + +hbalTreeNodes :: a -> Int -> [Tree a] + +fibs = 0 : 1 : zipWith (+) fibs (tail fibs) + +-- The minimum height for a balanced tree +minHeight n = ceiling $ logBase 2 $ fromIntegral (n + 1) + +-- The minimum node for a height +minNode h = fibs !! (h + 2) - 1 + +maxNode h = 2 ^ h - 1 +maxHeight n = (length $ takeWhile (<= n + 1) fibs) - 3 + + +hbalTreeNodes x n = [t | h' <- [minHeight n..maxHeight n], t <- build n h'] + where build _ 0 = [Empty] + build _ 1 = [Branch x Empty Empty] + build n h = let n' = n - 1 in + [Branch x lt rt | (h1, h2) <- [(h-2, h-1), (h-1, h-2), (h-1, h-1)] + , n1 <- [max (n' - maxNode h2) $ minNode h1.. + min (n' - minNode h2) $ maxNode h1] + , lt <- build n1 h1 + , rt <- build (n' - n1) h2] |