AVL Binary Heap(平衡测试) [英] AVL Binary Heap(Balanace test)

问题描述

我正在尝试通过一棵树测试是否是AVL树.

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.

这是我到目前为止的工作:

This is my work so far:

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?

序言-是否平衡树

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

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 Binary Heap(平衡测试)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！