AVL Binary Tree - Balanace test

Question

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?

score 1 · Answer 1 · answered Aug 30 '12 at 00:16

the code seems fairly ok, maybe indenting the data and using the same functors as found in the comment can help:

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.

Formatting by hand it's tedious. If you use SWI-Prolog, the IDE will do for you, just place a newline after each comma.

test:

?- t.
true.

My bad hadn't had my morning coffee yet. Yes I do get true. as well. — Anticipating, Aug 30 '12 at 07:17
@WillNess do you find the error in the code? It still gives true on that specific tree. Even drew it on paper to see if it was balanced and the comment in the post was just misleading. But it looks like a really unbalanced true on my paper at least. — Anticipating, Aug 30 '12 at 07:32

Will Ness · Accepted Answer · 2012-08-30T07:51:48.463

1

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

edited Aug 30 '12 at 07:51

answered Aug 30 '12 at 07:20

Will Ness

70,110
9
98
181

bit confused what is h() ? Isn't it possible to check it just one argument? I pref just sending in the tree to avoid human errors. – Anticipating Aug 30 '12 at 07:40
we get two possible outcomes out of `avl_height/2` in its 2nd arg. Either it is `h(X)` where `X` is its height, or it is `not`, signalling that this tree is not AVL. AVL tree is *almost* balanced. – Will Ness Aug 30 '12 at 07:43
I do it on the same tree I get the same output as if I do it on a tree that is balanced. – Anticipating Aug 30 '12 at 07:44
T= b(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)))))), N = h(1) This is the output I get if I input the tree that we're evaluating. – Anticipating Aug 30 '12 at 07:46
@Anticipating I fixed a typo. – Will Ness Aug 30 '12 at 07:52
Working for this tree now, wondering is it possible like I wrote in my prev question to just have one input parameter for the test? Or is the H variable in the function call mandatory? – Anticipating Aug 30 '12 at 07:54
Is it possible to do a nested call from a funciton with jsut the tree inparameter to this function(unnecessery code) but still, want to be able to have less human interaction with the code itself. – Anticipating Aug 30 '12 at 07:58
Reason for asking is because its part of an assignment from where I'm trying to learn from, so would pref to have just one input parameter. – Anticipating Aug 30 '12 at 08:03
@Anticipating you mean `is_AVL(T):- avl_height(T,h(_)).` ? – Will Ness Aug 30 '12 at 08:09
No like is it possible to make avl_height to only accept one input parameter? – Anticipating Aug 30 '12 at 10:06
@Anticipating then it makes no sense to me. it must get a tree and produce its height, or a "not" signal. If you intend to use it as a predicate, just use `is_AVL` that I showed you. You can always change names however you like, as long as you change them consistently. Have you picked an intro book to Prolog yet? :) – Will Ness Aug 30 '12 at 10:16
Not yet, scoping Internet so far. Binary heap might have been abit to much for a rookie like myself but I try to want to at least have a challenge. – Anticipating Aug 30 '12 at 10:19
@Anticipating http://stackoverflow.com/a/8685260/849891 and http://stackoverflow.com/a/10370903/849891 are excellent choices. :) Aso [this](http://stackoverflow.com/q/401635/849891) has more answers with many choices. – Will Ness Aug 30 '12 at 11:06

AVL Binary Tree - Balanace test

2 Answers2