build a tree with given number of nodes

user_8702185 0
Viewed 422

I have a datastructure for a tree with nodes that have either one or two childs. I can generate a random tree with a given maximum Depth. Now I want to generate these random three with a given maximum amount of nodes (/leafes). This is my structure:

import System.Random

data Tree a = Leaf 
            | NodeTwo (Tree a) (Tree a)
            | NodeOne (Tree a)
            deriving (Show)

create :: RandomGen g => Int -> Int -> Int -> Int -> g -> Tree a
create depth maxNodeOne maxNodeTwo maxLeaf g
    | (depth == 0) = Leaf
    | (x >= a && x < c && (maxNodeTwo /= 0)) 
      = let (g1, g2) = split g in 
      NodeTwo (create (depth -1) maxNodeOne (maxNodeTwo-1) 
      maxLeaf g1) (create (depth -1) maxNodeOne 
      (maxNodeTwo-1) maxLeaf g2) 
    |(x >= c && x < 2*c && (maxNodeOne /= 0))
     = NodeOne (create  (depth -1) 
    (maxNodeOne -1) maxNodeTwo maxLeaf g')
    | otherwise = Leaf
    where (x, g') = next g
          (a, b) = genRange g
          c = (b - a) `div` 3

countFnk :: Tree a -> Int             
countFnk (Leaf) = 0
countFnk (NodeOne a) = countFnk a
countFnk (NodeTwo a b) = 1 + countFnk a + countFnk b

countLam :: Tree a -> Int             
countLam (Leaf) = 0
countLam (NodeOne a) = 1 + countLam a
countLam (NodeTwo a b) = countLam a + countLam b

countLeaf :: Tree a -> Int             
countLeaf (Leaf) = 1
countLeaf (NodeOne a) = countLeaf a
countLeaf (NodeTwo a b) = countLeaf a + countLeaf b

This attempt fails ofcourse. I don't know how to decrement the counter(s) for the node(s) in the recursion. I also have functions which can get me the amount of nodes (/leafes) but I don't know how to use these functions in my create function since they need a finished tree to scan. Thanks for your help.

binary-tree tree nodes haskell
1 Answers

The most obvious problem is in your NodeTwo case. You arrive at that point with a "budget" of NodeTwos and NodeOnes to spend. But you tell both branches of your new tree the same thing: "feel free to spend the whole total budget"! Of course if they both do that, you will wind up spending double your budget.

You need some way to negotiate a budget for each branch of the tree. There are a number of ways you could do this; for example, give one branch access to the whole budget, and give whatever is left to the second branch. Or you could decide before creating either branch how to divide the budget between them, and give each branch only a portion of your total budget.

Either of those two approaches probably introduce some bias in your randomness, which may or may not matter to you. You should think of a way to handle the budget accounting in a way that produces the kinds of random trees you want.

Once you've fixed this, you'll run into other problems: there are constraint sets for which it is impossible to build a tree fitting them! Most notably, if maxLeaf is zero, you can't create any kind of tree at all, since every tree has at least one leaf node somewhere. You'll have to be careful not to build any subtrees with too few leaves available to let them terminate.

user_6254030
Related