1

ツリーがAVLツリーであるか、プロローグを使用していないかをテストしようとしています。

これまでに行ったテストで機能する高さテストを作成しましたが、バランステストはまだうまくいきません。

これはこれまでの私の仕事です：

avl('Branch'(LeftBranch,RightBranch)) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  abs(H1-H2) =< 1.

私はこのコードを古いstackoverflowコードに基づいています。ただし、すべての場合に機能するわけではありません。私の身長コードが含まれます。どこかで私は間違いを犯しました、そして私はそれをどこで見つけるか確信しています。

height(leaf(_),1).
height('Branch'(LeftBranch,RightBranch,H) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  H is max(H1,H2)+1.

なぜ私のコードはいくつかの木を評価しないのですか？

Prolog-バランスツリーかどうか

これは私がバラナスツリーのテストに基づいたスレッドであり、彼がコメントに投稿したツリーで試してみましたが、失敗しました。何かアイデアはありますか？

4

2 に答える 2

1

コードはかなり問題ないようです。データをインデントし、コメントにあるのと同じファンクターを使用すると役立つ場合があります。

t :- avl(b(l(1),
           b(l(2),
             b(l(3),
               b(l(4),
                 l(5)
                )
              )
            )
          ),
         b(l(6),
            b(l(7),
              b(l(8),
                b(l(9),
                  l(10)
                 )
             )
          )
        )
    ).

avl(LeftBranch,RightBranch) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  abs(H1-H2) =< 1.

height(l(_),1).
height(b(LeftBranch,RightBranch),H) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  H is max(H1,H2)+1.

手作業でフォーマットするのは面倒です。SWI-Prologを使用する場合は、IDEが自動的に機能し、各コンマの後に改行を配置するだけです。

テスト：

?- t.
true.
于 2012-08-30T00:16:35.850 に答える
1

AVLツリーの各ブランチは、まずAVLツリー自体であると想定されています。それが本当である場合にのみ、高さを比較する必要があります。

chacの答えのツリーは明らかに不均衡ですが、コードはそれを問題ないと見なします。そうではない。

次に、タイプミス。短い名前を使用すると、発生する可能性が低くなります。

avl_height(b(L,R),H) :-
  avl_height(L,h(H1)), 
  avl_height(R,h(H2)), 
  abs(H1-H2) =< 1, !,
  H3 is 1 + max(H1,H2), H=h(H3).

avl_height(b(_,_),not).

avl_height(l(_),h(1)).
于 2012-08-30T07:20:48.707 に答える