Search code examples
treeprologavl-treetree-balancing

AVL Binary Tree - Balanace test

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.

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 - Balanced tree or not

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?

Solution

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

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