AVL 二叉树 - 平衡测试 [英] AVL Binary Tree - Balanace test

问题描述

我正在尝试测试一棵树是 AVL 树还是不使用 prolog.

I'm trying to achieve a testing if a tree is AVL tree or not using prolog.

我已经做了一个高度测试，适用于我迄今为止所做的测试，但我的平衡测试仍然不强.

I've made a height test that works for the tests I've done so far but my balancing test is still not going strong.

这是我目前的工作:

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

我根据较旧的 stackoverflow 代码编写了此代码.但它并不适用于所有情况.将包括我的身高代码.我在某个地方犯了一个错误，我确定在哪里可以找到它.

I've based this code from an older stackoverflow code. But it doesn't work in all cases. Will include my height code. Somewhere I've made a misstake and Im sure where to find it.

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

为什么我的代码不对某些树进行评估?

Why doesn't my code evaluate for some trees?

Prolog - 平衡树与否

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

This was the thread I based my balanace tree test on, and I did try it with the tree he posted in the comments but i failed, any ideas?

推荐答案

AVL 树的每个分支首先应该是 AVL 树本身.只有在这种情况下，您才应该比较高度.

Each branch of an AVL tree is first of all supposed to be an AVL tree itself. Only if that is true should you compare the heights.

chac 的答案中的树显然是不平衡的，但是您的代码认为还可以.不是.

The tree in chac's answer is obviously unbalanced, but your code deems it OK. It is not.

然后是错别字.如果您使用短名称，则不太可能发生.

Then, the typos. If you use short names, less likely to happen.

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

这篇关于AVL 二叉树 - 平衡测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！