Prolog: Building a completely balanced tree

Does anyone know of any simpler ways of building completely bala开发者_StackOverflownced trees in Prolog?

Here's one solution I've found but I'm wondering if anyone knows of any simpler solutions?

This one is pretty simple but took me a little while to grasp exactly how it works.

Thanks :).

% from given solution

cbal_tree( 0, nil ) :- !.
cbal_tree( N, t(x,L,R) ) :- 
    N > 0,

    N0 is N - 1, % if N is 4, this would be 3

    N1 is N0 mod 2, % if N is 4, this would be 3 mod 2 = 1
    N2 is N0 - N1, % if N is 4, this would be 3-1= 2

    distrib( N1, N2, LeftNode, RightNode ),

    cbal_tree( LeftNode, L ), 
    cbal_tree( RightNode, R ).

distrib(N,N,N,N) :- !.
distrib(N1,N2,N1,N2). % giving these two clauses (*) 1,2,?,? could give 1,2 or 2,1
distrib(N1,N2,N2,N1). % (*)

The accepted answer is wrong.

Consider the case when N=5. The one subtree takes as argument the number 4 and the other the number 0. That is not a balanced tree.

Instead, I propose the following code:

cbal_tree(0, nil).
cbal_tree(N, t(x,L,R)) :-
    N > 0,
    N0 is N - 1,    % -1 to account for root node
    N1 is N0 div 2,
    N2 is N0 - N1,
    (N mod 2 =\= 0 -> permutation([N1,N2], [NLeft,NRight]) ;
                      [N1, N2] = [NLeft, NRight]),
    cbal_tree(NLeft, L),
    cbal_tree(NRight, R).

The if statement is to prevent backtracking from bringing you duplicate answers.

Please consider heavily marking this as an accepted answer because the answer provided is confusing at least.

This build symmetric trees:

symm_tree(nil,0).
symm_tree(t(L,R),Level) :-
    Level > 0,
    M is Level-1,
    symm_tree(L,M),
    symm_tree(R,M).

Adding labels to the nodes should be trivial.

The code you posted can be slightly simplified to

cbal_tree(0, nil).
cbal_tree(N, t(x,L,R)) :- 
    N > 0,
    N0 is N - 1,    % -1 to account for root node
    N1 is N0 mod 2,
    N2 is N0 - N1,

    permutation([N1,N2], [NLeft,NRight]),

    cbal_tree(NLeft, L),
    cbal_tree(NRight, R).

but this is really how simple it gets, and the distrib/3 handling of duplicates is gone.