0

Checking balance of binary trees c++

is It posible to make a c++ function that checks if a binary tree is avl without accessing the same node more than once?

23rd Apr 2018, 2:13 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
16 odpowiedzi
+ 3
Yes. It is possible using DFS algorithm. Try to run dfs on root of tree and recursive check the length of subtrees. It their lengths are different only by 1 on every vertex then it is avl. struct node { node * left, * right; }; int dfs(node * u) { int r1 = 0, r2 = 0; if (u->left) r1 = dfs(u->left); if (u->right) r2 = dfs(u->right); if (r1 == -1 || r2 == -1) return -1; if (abs(r1 - r2) < 2) return max(r1, r2); else return -1; } If this function returns -1 then it is not balanced tree. Otherwise, it is balanced.
23rd Apr 2018, 2:54 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
+ 2
Yes. Making a tree balanced is more difficult, but checking it is balanced shouldn't need multiple node visitations!
23rd Apr 2018, 2:53 PM
Emma
+ 2
Bartosz Pieszko Awesome ☺
23rd Apr 2018, 2:55 PM
Emma
+ 1
Xan thank you 😉
23rd Apr 2018, 2:55 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
thank you so much, but the Code isn't working for me. It always returns that it's a balanced tree.
23rd Apr 2018, 3:35 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
0
Juan Casanova Ltaif Do you have static binary tree or dynamic allocated? If it is static then you should change the code. However, I will check it in 1 hour because I'm going to train now.
23rd Apr 2018, 3:49 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
It's dynamic allocated, thank you for your time.
23rd Apr 2018, 3:52 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
0
Can you paste the full code to SoloLearns?
23rd Apr 2018, 3:53 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
this is what I have so far struct rep_binario { info_t dato; rep_binario *izq;//left rep_binario *der;//right }; bool es_vacio_binario(binario_t b) { return (b == NULL); } static int dfs(binario_t b){ int r1 = 0, r2 = 0; if (b->izq) r1 = dfs(b->izq); if (b->der) r2 = dfs(b->der); if(r1==-1||r2==-1) return -1; if(abs(r1-r2)<2) return max(r1,r2); else return -1; } bool es_AVL(binario_t b) {//the function I need if (es_vacio_binario(b)) return true; else return (dfs(b) != -1); }
23rd Apr 2018, 3:59 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
0
Is Binario_t a pointer on rep_binario?
23rd Apr 2018, 4:12 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
It is indeed. Sorry for the chaos, I had to copy the relevant parts. It has over 20 different functions
23rd Apr 2018, 4:14 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
0
Please paste code to pastebin.com and send link there if you can. I'll try to check what is wrong in 30 minutes
23rd Apr 2018, 4:16 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
the other functions work fine, this one is the only one that I can't seem to work arround. Mainly because of the "can't acces the same node twice" thing but I can send the rest of the Code if needed
23rd Apr 2018, 4:26 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
23rd Apr 2018, 4:29 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar
0
You should use pointers. Try change argument to rep_binario * b
23rd Apr 2018, 4:39 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
do you mean on dfs?
23rd Apr 2018, 4:59 PM
Juan Casanova Ltaif
Juan Casanova Ltaif - avatar