https://wiki.haskell.org/index.php?title=99_questions/Solutions/60&feed=atom&action=history99 questions/Solutions/60 - Revision history2024-03-19T10:43:41ZRevision history for this page on the wikiMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=99_questions/Solutions/60&diff=61365&oldid=prevWizzup: categorize2016-12-25T13:38:35Z<p>categorize</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:38, 25 December 2016</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 63:</td>
<td colspan="2" class="diff-lineno">Line 63:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> r <- baltree hr nr]</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> r <- baltree hr nr]</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Programming exercise spoilers]]</div></td>
</tr>
</table>Wizzuphttps://wiki.haskell.org/index.php?title=99_questions/Solutions/60&diff=36045&oldid=prevWapcaplet at 21:47, 13 July 20102010-07-13T21:47:11Z<p></p>
<p><b>New page</b></p><div>(**) Construct height-balanced binary trees with a given number of nodes<br />
<br />
Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain?<br />
<br />
Clearly, MaxN = 2**H - 1. However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a function <hask>minNodes</hask> that returns the minimum number of nodes in a height-balanced binary tree of height H.<br />
<br />
On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have? Write a function <hask>maxHeight</hask> that computes this.<br />
<br />
Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes. Find out how many height-balanced trees exist for N = 15.<br />
<br />
<haskell><br />
hbalTreeNodes _ 0 = [Empty]<br />
hbalTreeNodes x n = concatMap toFilteredTrees [minHeight .. maxHeight]<br />
where toFilteredTrees = filter ((n ==) . countNodes) . hbalTree x<br />
<br />
-- Similar to the Fibonacci sequence but adds 1 in each step.<br />
minNodesSeq = 0:1:zipWith ((+).(1+)) minNodesSeq (tail minNodesSeq)<br />
minNodes = (minNodesSeq !!)<br />
<br />
minHeight = ceiling $ logBase 2 $ fromIntegral (n+1)<br />
maxHeight = (fromJust $ findIndex (>n) minNodesSeq) - 1<br />
<br />
countNodes Empty = 0<br />
countNodes (Branch _ l r) = countNodes l + countNodes r + 1<br />
<br />
</haskell><br />
Another solution generates only the trees we want:<br />
<haskell><br />
-- maximum number of nodes in a weight-balanced tree of height h<br />
maxNodes :: Int -> Int<br />
maxNodes h = 2^h - 1<br />
<br />
-- minimum height of a weight-balanced tree of n nodes<br />
minHeight :: Int -> Int<br />
minHeight n = ceiling $ logBase 2 $ fromIntegral (n+1)<br />
<br />
-- minimum number of nodes in a weight-balanced tree of height h<br />
minNodes :: Int -> Int<br />
minNodes h = fibs !! (h+2) - 1<br />
<br />
-- maximum height of a weight-balanced tree of n nodes<br />
maxHeight :: Int -> Int<br />
maxHeight n = length (takeWhile (<= n+1) fibs) - 3<br />
<br />
-- Fibonacci numbers<br />
fibs :: [Int]<br />
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)<br />
<br />
hbalTreeNodes :: a -> Int -> [Tree a]<br />
hbalTreeNodes x n = [t | h <- [minHeight n .. maxHeight n], t <- baltree h n]<br />
where<br />
-- baltree h n = weight-balanced trees of height h with n nodes<br />
-- assuming minNodes h <= n <= maxNodes h<br />
baltree 0 n = [Empty]<br />
baltree 1 n = [Branch x Empty Empty]<br />
baltree h n = [Branch x l r |<br />
(hl,hr) <- [(h-2,h-1), (h-1,h-1), (h-1,h-2)],<br />
let min_nl = max (minNodes hl) (n - 1 - maxNodes hr),<br />
let max_nl = min (maxNodes hl) (n - 1 - minNodes hr),<br />
nl <- [min_nl .. max_nl],<br />
let nr = n - 1 - nl,<br />
l <- baltree hl nl,<br />
r <- baltree hr nr]<br />
</haskell></div>Wapcaplet