finish v6

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]