Difference between revisions of "99 questions/Solutions/55"
(cleanup/format solution code, added type signature and explanation) 

Line 6:  Line 6:  
<haskell> 
<haskell> 

+  cbalTree :: Int > [Tree Char] 

cbalTree 0 = [Empty] 
cbalTree 0 = [Empty] 

−  cbalTree n = 
+  cbalTree n = let (q, r) = (n  1) `quotRem` 2 
−  +  in [Branch 'x' left right  i < [q .. q + r], 

+  left < cbalTree i, 

+  right < cbalTree (n  i  1)] 

</haskell> 
</haskell> 

−  +  This solution uses a list comprehension to enumerate all the trees, in a style that is more natural than standard backtracking. 

+  
+  The base case is a tree of size 0, for which <tt>Empty</tt> is the only possibility. Trees of size <tt>n == 1</tt> or larger consist of a branch, having left and right subtrees with sizes that sum up to <tt>n  1</tt>. This is accomplished by getting the quotient and remainder of <tt>(n  1)</tt> divided by two; the remainder will be 0 if <tt>n</tt> is odd, and 1 if <tt>n</tt> is even. For <tt>n == 4</tt>, <tt>(q, r) = (1, 1)</tt>. 

+  
+  Inside the list comprehension, <tt>i</tt> varies from <tt>q</tt> to <tt>q + r</tt>. In our <tt>n == 4</tt> example, <tt>i</tt> will vary from 1 to 2. We recursively get all possible left subtrees of size <tt>[1..2]</tt>, and all right subtrees with the remaining elements. 

+  
+  When we recursively call <tt>cbalTree 1</tt>, <tt>q</tt> and <tt>r</tt> will both be 0, thus <tt>i</tt> will be 0, and the left subtree will simply be <tt>Empty</tt>. The same goes for the right subtree, since <tt>n  i  1</tt> is 0. This gives back a branch with no childrena "leaf" node: 

+  
+  <haskell> 

+  > cbalTree 1 

+  [Branch 'x' Empty Empty] 

+  </haskell> 

+  
+  The call to <tt>cbalTree 2</tt> sets <tt>(q, r) = (0, 1)</tt>, so we'll get back a list of two possible subtrees. One has an empty left branch, the other an empty right branch: 

+  
+  <haskell> 

+  > cbalTree 2 

+  [ 

+  Branch 'x' Empty (Branch 'x' Empty Empty), 

+  Branch 'x' (Branch 'x' Empty Empty) Empty 

+  ] 

+  </haskell> 

+  
+  In this way, balances trees of any size can be built recursively from smaller trees. 
Revision as of 21:01, 19 July 2010
(**) Construct completely balanced binary trees
In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.
Write a function cbaltree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.
cbalTree :: Int > [Tree Char]
cbalTree 0 = [Empty]
cbalTree n = let (q, r) = (n  1) `quotRem` 2
in [Branch 'x' left right  i < [q .. q + r],
left < cbalTree i,
right < cbalTree (n  i  1)]
This solution uses a list comprehension to enumerate all the trees, in a style that is more natural than standard backtracking.
The base case is a tree of size 0, for which Empty is the only possibility. Trees of size n == 1 or larger consist of a branch, having left and right subtrees with sizes that sum up to n  1. This is accomplished by getting the quotient and remainder of (n  1) divided by two; the remainder will be 0 if n is odd, and 1 if n is even. For n == 4, (q, r) = (1, 1).
Inside the list comprehension, i varies from q to q + r. In our n == 4 example, i will vary from 1 to 2. We recursively get all possible left subtrees of size [1..2], and all right subtrees with the remaining elements.
When we recursively call cbalTree 1, q and r will both be 0, thus i will be 0, and the left subtree will simply be Empty. The same goes for the right subtree, since n  i  1 is 0. This gives back a branch with no childrena "leaf" node:
> cbalTree 1
[Branch 'x' Empty Empty]
The call to cbalTree 2 sets (q, r) = (0, 1), so we'll get back a list of two possible subtrees. One has an empty left branch, the other an empty right branch:
> cbalTree 2
[
Branch 'x' Empty (Branch 'x' Empty Empty),
Branch 'x' (Branch 'x' Empty Empty) Empty
]
In this way, balances trees of any size can be built recursively from smaller trees.