<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Andrew Coppin wrote:
<blockquote cite="mid46717BCA.9090108@btinternet.com" type="cite">trees
:: [Int] -> [Tree]
<br>
trees = map fst . (\ts -> all_trees 1 (2 * length ts) ts) . map Leaf
<br>
<br>
all_trees :: Int -> Int -> [Tree] -> [(Tree,[Tree])]
<br>
all_trees n m ts
<br>
| n > m = []
<br>
| otherwise = pick ts ++ sub_trees n m ts
<br>
<br>
sub_trees :: Int -> Int -> [Tree] -> [(Tree,[Tree])]
<br>
sub_trees n m ts = do
<br>
let n2 = n * 2
<br>
(t0,ts0) <- all_trees n2 m ts
<br>
(t1,ts1) <- all_trees n2 m ts0
<br>
return (Branch t0 t1, ts1)
<br>
</blockquote>
<br>
Idiot...<br>
<br>
The size of the deepest possible <b>balanced</b> tree with N leaves is
log2 N. The deepest possible <b>unbalanced</b> tree has N nodes!<br>
<br>
For small N, it doesn't matter too much. But as N gets larger, the
difference becomes... uh... large? (!)<br>
<br>
*sigh* I hate being wrong. :-(<br>
<br>
</body>
</html>