プロローグ内でツリーがavl-treeであるかどうかを確認しています。エラー

Question

私のプログラムは正しく動作していません。テストしようとするとエラーが発生します。

テストのための私の例は：

if_avl_tree(t(t(t(nil/0, 3, nil/0)/1, 7, t(t(nil/0, 9, nil/0)/1, 11, nil/0)/2)/3, 16, t(nil/0, 25, t(nil/0, 40, nil/0)/1)/2)/4). 

これは私のコードです：

if_avl_tree(t(_,_,_)/_) :- T=t(_,_,_)/_ , is_binTree(T), if_avl_tree(T, _), !. 
if_avl_tree(nil/0, 0). 
if_avl_tree(t(nil/0,_, nil/0), 1). 
if_avl_tree(t(L,_,R)/H, Hh) :- if_avl_tree(L, H1), 
           if_avl_tree(R, H2), abs(H1 - H2) =< 1, !,                      
           H3 is 1 + max(H1,H2), H3=:=Hh. 

is_binTree(nil/0) :- !. 
is_binTree(t(L,_,R)/_):- is_binTree(L), is_binTree(R). 

そして、これは私のエラーです：

ERROR: Arguments are not sufficiently instantiated 
ERROR: In: 
ERROR: [10] 1=:=_6218 
ERROR: [8] if_avl_tree(t(...,16,...)/4) at e:/prolog/tasks/lab06tomashchuk.pl:50 
ERROR: [7] <user> 
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization. 
ERROR: Re-run your program in debug mode (:- debug.) to get more detail. 

Answer 1

あなたのサンプルコードは、正しい軌道に沿って間違いですしかし、いくつかのアノモリがあります。

のは、バイナリツリーの簡単な表現を見てみましょう：

btree(Value, Left, Right) 

これはかなり自明です。また、サブツリーがない場合は、nilというアトムを使用できます。

我々は構造がバイナリツリーであるかどうかを検証したい場合は、我々はこのようにそれを行うことができます。

is_binary_tree(nil). % Allow for a nil tree with no values 
is_binary_tree(btree(_, Left, Right)) :- 
    is_binary_tree(Left), 
    is_binary_tree(Right). 

任意のノードの2つのつの子サブツリーの高さは、時によって異なる場合バイナリーツリーはAVLですほとんどの人。バイナリツリーの表現はまだのように、ツリー表現の一環として、各ツリーの高さを持っている場合：

btree(Value, Left, Right)/Height 

そして、ツリーの内容や構造が変更されたときにHeightが維持されると仮定しなければなりません。彼らが変更されていない場合は、それがAVLツリーであるかどうかの決定は、持ち歩くために余分な高さ引数を必要としません。高さはすでに事前に計算され、維持されているので、彼らはのみチェックする必要があります。

is_AVL_tree(nil/0). 
is_AVL_tree(btree(_, Left, Right)/_) :- 
    Left = btree(_, _, _)/HeightLeft, 
    Right = btree(_, _, _)/HeightRight, 
    abs(HeightLeft - HeightRight) =< 1, 
    is_AVL_tree(Left), 
    is_AVL_tree(Right). 

あなたはそれが上記の二つのルールでの世話をしています1の高さのために別々の基本ケースを必要としません。

用語の引数としてツリーのメンテナンスによって決められた高さを持たない場合は、高さを引数として持ち上げて計算する必要があります。木表現の一部として必要ではない。それは冗長であり、ルールを不必要に乱雑にする。

is_AVL_tree(nil, 0). 
is_AVL_tree(btree(_, Left, Right), Height) :- 
    is_AVL_tree(Left, HeightLeft), 
    is_AVL_tree(Right, HeightRight), 
    abs(HeightLeft - HeightRight) =< 1, 
    Height is 1 + max(HeightLeft, HeightRight).