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

したがって 、新しい要素を新しい AVL ツリーaddavl(Tree, Element, NewTree/Height)の生成に追加する述語があります。Tree

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与えられた不透明な述語として使用し、その定義を再検討しないことです。

2 つのリストL1と(位置を 1 つずらした) の間で論理変数を共有することは、最終ステップで完全なツリーが構築されるまで、L2計算のあるステップから次のステップに蓄積された結果を渡すように手配するのに役立ちます。これは利便性のための取引効率です。特に要素のリストが長くなると予想される場合は、これを直接再帰スタイルで再実装する必要があります。nil/0Tree

注:maplist直接再帰ソリューションを使用するか手動でロールするかは、構文上の問題です。addavl両方のバリアントは、前の呼び出しの出力を次の呼び出しへの入力として使用して、 を呼び出してツリーに要素を徐々に追加する同じ反復計算プロセスを記述します。たとえば Haskell では、偶然にも、一般的なpatternは、驚き! - iterate.

(これはもちろん、より高いレベルでのみ当てはまります。具体的な実装では、SWI Prolog のように、一方を他方よりもはるかに最適化できます。ここでリストを使用すると、おそらく他のバリアントよりも効率が低下します)。

于 2013-04-29T17:49:25.903 に答える