Пролог: Построение полностью сбалансированного дерева

Question

Кто-нибудь знает какие-либо более простые способы построения полностью сбалансированных деревьев в Прологе?

Вот одно решение, которое я нашел, но мне интересно, кто-нибудь знает какие-нибудь более простые решения?

Это довольно просто, но мне понадобилось немного времени, чтобы понять, как именно это работает.

Спасибо:).

% 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). % (*)

Answer 1

Принятый ответ неверен.

Рассмотрим случай, когда N = 5. Одно поддерево принимает в качестве аргумента число 4, а другое - число 0. Это не сбалансированное дерево.

Вместо этого я предлагаю следующий код:

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).

Оператор if должен предотвращать дублирование ответов при возврате.

Пожалуйста, подумайте о том, чтобы пометить это как принятый ответ, поскольку предоставленный ответ, по крайней мере, сбивает с толку.

Answer 2

Это построение симметричных деревьев:

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

Добавление меток к узлам должно быть тривиальным.

Код, который вы разместили, можно немного упростить до

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).

но это действительно так просто, и distrib/3 обработка дубликатов прекращена.