Vérifie si l'arborescence est avl-tree dans prolog. erreur

Question

Mon programme ne fonctionne pas correctement. Quand j'essaie de le tester, j'ai une erreur.

Mon exemple pour les tests:

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

Voici mon code:

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

Et voici mon erreur:

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

Votre exemple de code est sans aucun doute le long de la bonne voie , mais a quelques anomolies.

Commençons par une représentation simple pour un arbre binaire:

btree(Value, Left, Right) 

Ceci est assez explicite. Et s'il n'y a pas de sous-arbre, l'atome nil peut être utilisé.

Si nous voulons valider si une structure est un arbre binaire, nous pouvons le faire de cette façon:

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

Un arbre binaire est AVL si les hauteurs des deux sous-arbres de l'enfant d'un nœud diffèrent d'au le plus un. Si votre représentation arborescente binaire a déjà la hauteur de chaque arbre dans le cadre de la représentation des arbres, comme ceci:

btree(Value, Left, Right)/Height 

Ensuite, il faut considérer la Height est maintenue lorsque le contenu de l'arbre ou la structure est modifiée. Si elles ne sont pas modifiées, la décision de savoir s'il s'agit d'un arbre AVL ne nécessite pas d'argument de taille supplémentaire. Les hauteurs sont déjà pré-calculés et maintenus, de sorte qu'ils ne doivent être vérifiés:

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

Vous n'avez pas besoin d'un cas de base distincte pour une hauteur de 1. Il est pris en charge par les deux règles ci-dessus.

Si vous n'avez pas les hauteurs prédéterminées par la maintenance de l'arbre comme argument dans le terme, alors nous aurons besoin d'avancer les hauteurs comme argument et de les calculer. Ce n'est pas nécessaire dans le cadre de la représentation arborescente. Ce serait redondant et rendrait les règles inutilement désordonnées.

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