AVL二元堆（Balanace测试）(AVL Binary Heap(Balanace test))

我想实现一个测试，如果树是AVL树或者是不使用序言。

我做了一个高度测试，对我迄今所做的测试工作，但我的动平衡试验仍不强劲。

这是我的工作至今：

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

我已经根据从旧计算器代码此代码。不过，这并不适用于所有情况。包括我的身高代码。那个我做了一个misstake和Im知道在哪里可以找到它。

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

为什么没有我的代码评估一些树木？

序言-平衡树或不

这是我根据我balanace树测试的线程，我与他张贴在评论树尝试，但我失败了，任何想法？

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

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会为你做，只需将每个逗号后换行。

测试：