Как определить, сбалансировано ли двоичное дерево?

О каком дереве ты говоришь? Есть самобалансирующиеся деревья там. Проверьте свои алгоритмы, где они определяют, нужно ли им переупорядочивать дерево, чтобы поддерживать баланс.

Ну, вам нужен способ определения высоты слева и справа, а также если баланс слева и справа сбалансирован.

И я бы просто возвратил высоту (узел-> слева) == высоту (узел-> справа);

Что касается написания функции height , прочитайте: Понимание рекурсии

Если это для вашей работы , я предлагаю:

1. не изобретать велосипед и
2. используют / покупают COTS вместо того, чтобы возиться с битами.
3. Сэкономьте свое время и силы для решения бизнес-задач.

Балансировка обычно зависит от длины самого длинного пути в каждом направлении. Приведенный выше алгоритм не собирается делать это для вас.

Что вы пытаетесь реализовать? Вокруг есть самобалансирующиеся деревья (AVL / Красно-черный). На самом деле, деревья Java сбалансированы.

What balanced means depends a bit on the structure at hand. For instance, A B-Tree cannot have nodes more than a certain depth from the root, or less for that matter, all data lives at a fixed depth from the root, but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven. Skip-lists Have no notion at all of balance, relying instead on probability to achieve decent performance. Fibonacci trees purposefully fall out of balance, postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates. AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant.

All of these structures and more are present in the standard libraries of most common programming systems (except python, RAGE!). Implementing one or two is good programming practice, but its probably not a good use of time to roll your own for production, unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections.

Это только определяет, сбалансирован ли верхний уровень дерева. То есть, у вас может быть дерево с двумя длинными ветвями далеко слева и далеко справа, но ничего посередине, и это вернет истину. Вам необходимо рекурсивно проверить root.left и root.right , чтобы узнать, сбалансированы ли они и перед возвращением true.

Разве это не сработает?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Любое несбалансированное дерево всегда не сработает.

Вот версия, основанная на общую глубину прохождения. Должно быть быстрее, чем другой правильный ответ и обрабатывать все упомянутые «проблемы». Извиняюсь за стиль, я не знаю, Java.

Вы все равно можете сделать его намного быстрее, возвращаясь рано, если Max и Min есть набор, и имеет значение> 1.

public boolean isBalanced( Node root ) {
    int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
    if ( root == null ) return true;
    while ( root != null ) {
        if ( root.left == null || root.right == null ) {
            maxLeaf = max( maxLeaf, curDepth );
            minLeaf = min( minLeaf, curDepth );
        }
        if ( root.left != null ) {
            curDepth += 1;
            root = root.left;
        } else {
            Node last = root;
            while ( root != null
             && ( root.right == null || root.right == last ) ) {
                curDepth -= 1;
                last = root;
                root = root.parent;
            }
            if ( root != null ) {
                curDepth += 1;
                root = root.right;
            }
        }
    }
    return ( maxLeaf - minLeaf <= 1 );
}

Бонусные упражнения. Простое решение. Очевидно, что в реальной реализации можно обойти это или что-то, чтобы не требовать пользователя включить высоту в своем ответе.

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     

Вы можете прочитать

F # типы функций: веселье с кортежами и каррингом

Вы должны поместить все переключатели группы в один и тот же контейнер, например GroupBox или Panel.

Наткнулся на этот старый вопрос во время поиска чего-то другого. Я замечаю, что вы так и не получили полного ответа.

Способ решения этой проблемы состоит в том, чтобы начать с написания спецификации для функции, которую вы пытаетесь записать.

Спецификация: Хорошо сформированное двоичное дерево считается «сбалансированным по высоте», если (1) оно пустое, или (2) его левый и правый потомки сбалансированы по высоте, и высота левого дерева находится в пределах 1 от высоты правого дерева.

Теперь, когда у вас есть спецификация, код является тривиальным для записи. Просто следуйте спецификации:

IsHeightBalanced(tree)
    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

Перевод этого на выбранный вами язык программирования должен быть тривиальным.

Бонусное упражнение : этот наивный набросок кода слишком много раз пересекает дерево при вычислении высоты. Можете ли вы сделать его более эффективным?

Супер бонусное упражнение : предположим, дерево массово несбалансировано. Например, миллион узлов глубоко с одной стороны и три глубоко с другой. Есть ли сценарий, в котором этот алгоритм сдувает стек? Можете ли вы исправить реализацию так, чтобы она никогда не сдувала стек, даже когда дано массово несбалансированное дерево?

UPDATE : Donal Fellows точек в своем ответе, что есть разные определения «сбалансированных», которые можно выбрать. Например, можно принять более строгое определение «сбалансированной высоты» и потребовать, чтобы длина пути к ближайшему пустому потомку находилась в пределах одного из путей к самому удаленному пустому потомку. Мое определение менее строгое, чем это, и поэтому допускает больше деревьев.

Можно также быть менее строгим, чем мое определение; можно было бы сказать, что сбалансированное дерево - это дерево, в котором максимальная длина пути к пустому дереву на каждой ветви отличается не более чем на две, или на три, или на какую-то другую константу. Или максимальная длина пути составляет часть минимальной длины пути, например, половину или четверть.

Обычно это не имеет значения. Точка любого алгоритма балансировки дерева состоит в том, чтобы гарантировать, что вы не окажетесь в ситуации, когда у вас есть миллион узлов с одной стороны и три с другой. Определение Донала прекрасно в теории, но на практике это боль, возникающая при использовании алгоритма балансировки деревьев, который соответствует этому уровню строгости. Экономия на производительности обычно не оправдывает затрат на внедрение. Вы тратите много времени на ненужные перестановки деревьев, чтобы достичь такого уровня равновесия, который на практике не имеет большого значения. Кого волнует, если иногда требуется сорок ветвей, чтобы добраться до самого дальнего листа в миллионном узле несовершенно сбалансированного дерева, когда теоретически оно может занять всего двадцать в идеально сбалансированном дереве? Дело в том, что на это никогда не уходит миллион.Получить от худшего случая миллион вниз до худшего случая сорок, как правило, достаточно хорошо; вы не должны идти все пути к оптимальному делу.

Вот то, что я пробовал в бонусном упражнении Эрика. Я пытаюсь раскрутить свои рекурсивные циклы и возвращаться, как только нахожу поддерево быть не сбалансированным.

int heightBalanced(node *root){
    int i = 1;
    heightBalancedRecursive(root, &i);
    return i; 
} 

int heightBalancedRecursive(node *root, int *i){

    int lb = 0, rb = 0;

    if(!root || ! *i)  // if node is null or a subtree is not height balanced
           return 0;  

    lb = heightBalancedRecursive(root -> left,i);

    if (!*i)         // subtree is not balanced. Skip traversing the tree anymore
        return 0;

    rb = heightBalancedRecursive(root -> right,i)

    if (abs(lb - rb) > 1)  // not balanced. Make i zero.
        *i = 0;

    return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}

Баланс - это действительно тонкое свойство; вы думаете, что знаете, что это такое, но так легко ошибиться. В частности, даже (хороший) ответ Эрика Липперта неверен. Это потому, что понятия высоты недостаточно. Вам необходимо иметь представление о минимальной и максимальной высоте дерева (где минимальная высота - это наименьшее количество шагов от корня до листа, а максимальное - это ... ну, вы поняли). Учитывая это, мы можем определить баланс как:

Дерево, в котором максимальная высота любой ветви не более чем на один больше минимальной высоты любой ветви.

(На самом деле это означает, что ветви сами сбалансированы; вы можете выбрать одну и ту же ветвь как для максимума, так и для минимума.)

Все, что вам нужно сделать, чтобы проверить это свойство, - это простой обход дерева с отслеживанием текущей глубины . При первом возврате это дает вам базовую глубину.Каждый раз после этого, когда вы возвращаетесь, вы сравниваете новую глубину с базовой линией

• , если она равна базовой линии, затем вы просто продолжаете
• , если это более чем одно другое, дерево не сбалансировано
• если это один раз, то теперь вы знаете диапазон для баланса, и все последующие глубины (когда вы собираетесь вернуться) должны быть либо первым, либо вторым значением.

В коде:

class Tree {
    Tree left, right;
    static interface Observer {
        public void before();
        public void after();
        public boolean end();
    }
    static boolean traverse(Tree t, Observer o) {
        if (t == null) {
            return o.end();
        } else {
            o.before();
            try {
                if (traverse(left, o))
                    return traverse(right, o);
                return false;
            } finally {
                o.after();
            }
        }
    }
    boolean balanced() {
        final Integer[] heights = new Integer[2];
        return traverse(this, new Observer() {
            int h;
            public void before() { h++; }
            public void after() { h--; }
            public boolean end() {
                if (heights[0] == null) {
                    heights[0] = h;
                } else if (Math.abs(heights[0] - h) > 1) {
                    return false;
                } else if (heights[0] != h) {
                    if (heights[1] == null) {
                        heights[1] = h;
                    } else if (heights[1] != h) {
                        return false;
                    }
                }
                return true;
            }
        });
    }
}

Я полагаю, вы могли бы сделать это без использования паттерна «Наблюдатель», но мне легче рассуждать таким образом.

[EDIT]: Почему нельзя просто взять высоту каждой стороны? Рассмотрим это дерево:

        /\
       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   C  /\     /   \
 /  \    /  \   /\   /\
A    B  D    E F  G H  J

Хорошо, немного беспорядочно, но каждая сторона корня сбалансирована: C - глубина 2, A , B , D , E - глубина 3, а F , G , H , J - глубина 4. Высота левой ветви равна 2 (помните, что высота уменьшается по мере того, как вы пересекаете ветвь), высота правой ветви равна 3. Тем не менее, общее дерево не сбалансировано, поскольку есть разница в высоте 2 между C и F . Вам нужна минимаксная спецификация (хотя реальный алгоритм может быть менее сложным, поскольку должно быть только две разрешенные высоты).