Hello, I have my own, student version of the implementation of a binary tree, and my task is to check whether it is balanced. If I understand correctly, if not, please correct me, then a balanced tree can be considered if, - any vertex has a difference in the lengths of the right subtree and the left one by no more than 1. And the fact is that my tree which I have to check for balance , is actually not balanced and its nodes look like this:

class Leaf<E> implements Comparable<E> { private Leaf<E> parent; private Leaf<E> right; private Leaf<E> left; private E element; private Leaf(E element) { this.element = element; } public E getElement() { return element; } @Override public int compareTo(Object obj) { Leaf<E> node = (Leaf<E>) obj; return this.hashCode() - node.hashCode(); } @Override public int hashCode() { int hash = 31; hash = hash * 17 + element.hashCode(); return hash; } }

And as you can see from the code, I have no balance factor , of course, because the tree is not balanced.

And my question is: how can I check whether the tree is balanced or not? Do I have to go all over the tree? And if it happens to be balanced by chance, for example, it has only one value, or the order of addition was such that it turned out to be a balance, but as a data structure, is it not balanced? How can I find out for sure in the spirit of:

 boolean isBalanced(Если надо) { return хитрый алгоритм проверки; }

I would be very grateful for any constructive thoughts on this issue.

  • one
    1. Yes, you need to go around the whole tree and compare the height of the subtrees. 2. In order for a tree not to be immediately balanced, with a test, elements should be added to it in the same order (descending or increasing). - Regent

1 answer 1

Yes, it will be a complete bypass of the tree. Recursion from two subtrees.

 public boolean isBalanced() { // ... return isBalanced(left) && isBalanced(right); }

PS And you do not need to keep the parent in the node. In 99% of cases, you can do without it.