프롤로그에서 트리가 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). 

노드의 두 자식 하위 트리의 높이가에 의해 다른 경우 이진 트리 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).