AVL Binary Heap (тест Balanace)

Question

Я пытаюсь достичь тестирования, если дерево является деревом 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 - Balanced tree or not

Это нить я на основе моего balanace тест дерева, и я сделал попробовать его с деревом он писал в комментариях, но я не удалось, какие-то идеи?

Answer 1

Каждая ветвь дерева AVL, в первую очередь должно быть само дерево AVL. Только если это так, вы должны сравнить высоты.

Дерево в ответе чака, очевидно, неуравновешенное, но ваш код считает это ОК. Это не.

Затем опечатки. Если вы используете короткие имена, менее вероятно.

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

Answer 2

код выглядит довольно хорошо, возможно отступы данных и с использованием тех же функторов, которые содержатся в комментарии может помочь:

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.