13
Фев
2017

Проверить является ли дерево сбалансированным

У меня есть свой, ученический вариант реализации двоичного дерева, и у меня задание проверить является ли оно сбалансированным. Если я правильно понял, если нет, пожалуйста поправьте меня, то сбалансированным дерево можно считать если, - любая вершина имеет разницу в длинах правого поддерева и левого, не больше чем на 1. И дело в том что мое дерево которое я должен проверить на сбалансированность, на самом деле не сбалансированное и его узлы выглядят так:

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;
    }
}

И как можно увидеть из кода, никакого balance factor у меня нет, разумеется, ведь дерево не сбалансированное.

И мой вопрос: как мне проверить является ли дерево сбалансированным или нет? Неужели мне придется проходить по всему дереву? А если оно случайно окажется сбалансированным, на пример в нем всего одно значение, или порядок добавления оказался таким, что в нем баланс получился, но как структура данных оно не сбалансированное? Как мне точно это выяснить в духе:

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

Буду очень признателен за любые, конструктивные мысли по этому вопросу.

Источник: https://ru.stackoverflow.com/questions/627113/%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%82%D1%8C-%D1%8F%D0%B2%D0%BB%D1%8F%D0%B5%D1%82%D1%81%D1%8F-%D0%BB%D0%B8-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE-%D1%81%D0%B1%D0%B0%D0%BB%D0%B0%D0%BD%D1%81%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%BC

Share

Тебе может это понравится...