AVL二进制树-Balanace测试

Question

我正在尝试测试一个树是AVL树还是不使用prolog。

我做了一个身高测试，适用于我迄今为止所做的测试，但我的平衡测试仍然不太好。

这是我迄今为止的工作：

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-平衡树或非

这是我基于平衡树测试的线程，我确实用他在评论中发布的树进行了尝试，但我失败了，有什么想法吗？

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就可以了，只需在每个逗号后面放一个换行符。

测试：

?- t.
true.