-1

我正在研究 Prolog，我发现很难实现一个谓词，它需要一个列表并从中构建一个平衡树。

我已经实现了这些构建AVL 树的谓词（我从 Bratko 书中获取了它，它工作正常）：

%%%  A program for constructing and searching an avl tree.

%%%  Based on Bratko pp 244ff. 

%%%  Build the tree. 

%% The root of the tree is Key.

addavl( nil/0, Key, avl(nil/0, Key, nil/0)/1 ).    

addavl( avl(Left, Y, Right)/Hy, Key, NewTree):-
    eq(Y, Key),
    !,
    NewTree = avl(Left, Y, Right)/Hy.

addavl( avl(Left, Y, Right)/Hy, Key, NewTree):-
    gt(Y, Key),
    addavl(Left, Key, avl(Left1, Z, Left2)/_ ),
    combine(Left1, Z, Left2, Y, Right, NewTree).  

addavl( avl(Left, Y, Right)/Hy, Key, NewTree):-
    gt(Key, Y),
    addavl(Right, Key, avl(Right1, Z, Right2)/_ ),
    combine(Left, Y, Right1, Z, Right2, NewTree).  

combine(T1/H1, A, avl(T21, B, T22)/H2 , C, T3/H3,
        avl(avl(T1/H1, A, T21)/Ha, B, avl(T22, C, T3/H3)/Hc)/Hb ):-
    H2 > H1,
    H2 > H3,
    Ha is H1 + 1,
    Hc is H3 + 1,
    Hb is Ha + 1.

combine(T1/H1, A, T2/H2, C, T3/H3,
        avl(T1/H1, A, avl(T2/H2, C, T3/H3)/Hc)/Ha ):-
    H1 >= H2,
    H1 >= H3,
    max1(H2, H3, Hc),
    max1(H1, Hc, Ha).

combine(T1/H1, A, T2/H2, C, T3/H3,
        avl(avl(T1/H1, A, T2/H2)/Ha, C, T3/H3)/Hc ):-
    H3 >= H2,
    H3 >= H1,
    max1(H1, H2, Ha),
    max1(Ha, H3, Hc).

max1(U, V, Max):-
    (  U > V,
       !,
       Max is U + 1
    ;  Max is V + 1
    ). 

eq(X, Y):-
    X == Y,
    !,
    write(X),
    write(' Item already in tree\n').

所以我有 addavl(Tree, Element, NewTree/Height)将新元素添加到Tree生成新 AVL 树的谓词。

现在我想创建一个新的谓词，它使用这个addavl/3谓词从元素列表中创建一个新的 AVL 树。

例如，如果我有 list: [1,2,3]，这个新谓词会创建一个包含元素1,2,3的新 AVL 树。

我正在尝试这样做，但我发现这样做有些困难。

我已经实现了这样的东西（但它不起作用）：

%% BASE CASE: The list is empty, so there is no element to insert 
%%            into the AVL Tree: 

buildTreeList(Tree, [], NewTree, Height) :- !.


%% If I am inserting the first element in the AVL Tree 
%% the hight H of the Tree after the insertion is 1: 

buildTreeList(Tree, [Head|Tail], NewTree, 1) :-  
    addavl(nil/0, Head, avl(nil/0, Head, nil/0)/H),
    Tree = nil/0,
    NewTree = avl(nil/0, Head, nil/0)/1,
    buildTreeList(NewTree, Tail, NT, Height).

buildTreeList(Tree, [Head|Tail], NewTree, H) :- 
    addavl(Tree, Head, avl(Tree, Head, NewTree)/H),
    buildTreeList(NewTree, Tail, NT, Height).

我的想法是：addavl/3谓词向新的 AVL 树添加一个元素，并给我这棵新树的高度（因为我有一对NewTree/Height）。

所以我的想法是：

  1. 滚动项目列表直到出现空列表（基本情况：列表中没有项目，所以我不会在 AVL 树中插入任何内容）

  2. 将列表的任何元素插入 AVL 树。

  3. 如果 AVL 树是空的，height=0那么我将通过以下方式创建一个新的 AVL 树：

     addavl(nil/0, Head, avl(nil/0, Head, nil/0)/H)

  4. 如果 AVL 树不为空，我将插入其中。

但它不起作用，可能是做这件事的错误方法。

有人可以帮助我吗？

4

1 回答 1

2

您正在尝试重新实现maplist/N.

你有addavl(Tree, Element, NewTree). 树木已经形成T/Height。您必须从nil/0.

buildTree(List,Tree):-
  length(List, N), 
  length(L1, N), append(L1, [Tree], [nil/0 | L2]),
  maplist( addavl, L1, List, L2).

（未测试）。

关键是，addavl/3用作给定的、不透明的谓词，不要重新审视它的定义。

两个列表之间共享逻辑变量L1和L2（移动一个位置）用于安排将累积结果从计算的一个步骤传递到下一个步骤，用 表示nil/0，直到Tree在最后一步构建完整的树。这是为了方便交易效率。您应该以直接递归的方式重新实现这一点，尤其是在预计元素列表很长的情况下。

注意：是否使用maplist或手动滚动直接递归解决方案，是一个语法问题。两种变体都描述了相同的迭代计算过程，即通过调用 将元素逐步添加到树中addavl，使用前一个调用的输出作为下一个调用的输入。巧合的是，一个常见的模式，例如在 Haskell 中，是用一个名为 - 惊喜的高阶过程捕获的。- iterate。

（当然，这仅在更高级别上是正确的。在具体实现中，如 SWI Prolog，一个可以比另一个优化得更好。在这里使用列表可能会比其他变体效率低）。

于 2013-04-29T17:49:25.903 回答