Создайте все возможные деревья AVL, используя список элементов в Прологе

Question

Учитывая список элементов, вернуть все возможные сбалансированные двоичные деревья, содержащие точно элементы этого списка. В нашем случае допустимое дерево имеет конструкцию: tree(_, left, right). Например:

?- avl_tree_planter(X, [yin, yang]).
X = tree(yang, tree(yin, nil, nil), nil) ;
X = tree(yin, tree(yang, nil, nil), nil) ;
X = tree(yin, nil, tree(yang, nil, nil)) ;
X = tree(yang, nil, tree(yin, nil, nil)) ;

Я попытался вывести все возможные варианты, используя обходы inorder, preorder и postorder:

abs_diff(L,R,D) :- D is L-R, L >= R.
abs_diff(L,R,D) :- D is R-L, R >= L.

height(nil,0).
height(tree(_,L,R), H) :- 
    height(L,HL), height(R,HR), 
    max_num(HL,HR,MaxH), H is MaxH + 1.

avl_tree_planter(nil,[]).
avl_tree_planter(tree(X,L,R), Xs) :-
    height(L,HL), height(R,HR),
    abs_diff(HL,HR,Diff), Diff =< 1, 
    avl_tree_planter(L,Ls), avl_tree_planter(R,Rs), 
    append(Ls,[X|Rs],Xs).     % inorder
avl_tree_planter(tree(X,L,R), Xs) :-  
    height(L,HL), height(R,HR),
    abs_diff(HL,HR,Diff), Diff =< 1,
    avl_tree_planter(L,Ls), avl_tree_planter(R,Rs), 
    append(Rs, [X], Xs1),     % postorder
    append(Ls, Xs1, Xs).  
avl_tree_planter(tree(X,L,R), Xs) :-  
    height(L,HL), height(R,HR),
    abs_diff(HL,HR,Diff), Diff =< 1,
    avl_tree_planter(L,Ls), avl_tree_planter(R,Rs), 
    append([X|Ls], Rs, Xs).   % preorder

В некоторых онлайн-интерпретаторах для ввода:

avl_tree_planter(X,[a,b]).

он выводит:

X = tree(a, nil, tree(b, nil, nil))

двенадцать раз, а затем переходит к бесконечному l oop, а в другом он повторяется бесконечно.

Я поставил условие остановки для рекурсия, так что я делаю не так?

Answer 1

Причина, по которой это застревает c в infinte l oop, заключается в том, что ваш height/2 использует метод генерации и проверки : сначала он создает дерево, а затем проверяет если высота соответствует требуемой высоте. Но по мере того, как деревья становятся все больше и больше, в конечном итоге ваша проверка начнет отклонять эти деревья, но нет никакого способа, чтобы ваш предикат прекратил предлагать новые деревья.

Мы можем построить деревья AVL, в которых каждый узел имеет Разница не более чем в один следующий:

:- use_module(library(clpfd)).

height(nil, 0).
height(tree(_, L, R), H) :-
    H #> 0,
    H1 #= H-1,
    H2 #= H-2,
    (
        (height(L, H1), height(R, H1));
        (height(L, H1), height(R, H2));
        (height(L, H2), height(R, H1))
    ).

Теперь мы можем генерировать деревья и «помечать» узлы этих деревьев дополнительными элементами. Это может помочь сделать более общий c предикат height/3, который экспортирует список переменных:

height(T, H, N) :-
    height(T, H, N, []).

height(nil, 0, N, N).
height(tree(X, L, R), H, [X|Ni], No) :-
    H #> 0,
    H1 #= H-1,
    H2 #= H-2,
    (
        (height(L, H1, Ni, Nt), height(R, H1, Nt, No));
        (height(L, H1, Ni, Nt), height(R, H2, Nt, No));
        (height(L, H2, Ni, Nt), height(R, H1, Nt, No))
    ).

Например:

?- height(T, 2, N).
T = tree(_622, tree(_642, nil, nil), tree(_662, nil, nil)),
N = [_622, _642, _662] ;
T = tree(_622, tree(_642, nil, nil), nil),
N = [_622, _642] ;
T = tree(_622, nil, tree(_642, nil, nil)),
N = [_622, _642] ;
false.

Я оставляю это как упражнение для пометьте дерево элементами в списке.