5
How can I understand a balanced binary tree and a perfect binary tree?
2 answers
7
Yes, as the name says a perfect binary tree has all its uniform nodes, having no imbalance, so it is always connected to 2 nodes (except the last one which evidently may have only one). It’s perfectly balanced. It’s too much work for the algorithm to keep this up and it’s not usually worth the effort. Something like this:
5
/ \
3 7
/ \ / \
1 4 6 8
The balanced binary tree admits a 1-level imbalance. It can be like this:
5
/ \
3 7
/ \ \
1 4 8
One more level below 8 would not be admitted and the tree would be unbalanced.
3
An addition to Maniero’s answer is that a perfect binary tree is always balanced but the opposite is not true. The main characteristic of a perfect tree is to have the total number of nodes belonging to the set {1, 3, 7, 15, 31, 63, ..., 2 (n+1)-1}, being n height, so all leaves will be on the same level. A balanced tree takes into account the balancing fact of each node, which can take -1.0 or 1, to get the factor of a node you make the difference of the left and right height of that node. ( This factor can be treated as modular can also be admitted in some only 0 or 1).
I recommend this site: https://sites.google.com/site/esdicapsi/estruturas-dinamicas/arvores-binarias
That video: https://www.youtube.com/watch?v=YkF76cOgtMQ&list=PLxI8Can9yAHf8k8LrUePyj0y3lLpigGcl&index=21
Browser other questions tagged terminology
You are not signed in. Login or sign up in order to post.
Every perfect tree is then balanced?
– Carlos
In its balanced tree. If you remove sheet 1 it remains balanced?
– Carlos
Yeah, it’s perfectly balanced. In this case taking would remain balanced, but putting depends on the place, precisely there would in some case require a rebalancing. Perfect requires rebalancing in many situations because only the last level can be unbalanced (there is no way to require everyone to be).
– Maniero