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

Question

Это было время с тех школьных лет. Получил работу в качестве специалиста по ИТ в больнице. Попытка двигаться, чтобы заняться программированием. Сейчас я работаю над бинарными деревьями, и мне было интересно, как лучше определить, сбалансировано ли дерево по высоте.

Я думал о чем-то подобном:

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

Это хорошая реализация? или я что-то упустил?

Answer 1

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

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

Спецификация: правильно сформированное двоичное дерево называется «сбалансированным по высоте», если (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)

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

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

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

ОБНОВЛЕНИЕ : Донал Феллоуз отмечает в своем ответе, что существуют различные определения «сбалансированного», которые можно выбрать. Например, можно взять более строгое определение «сбалансированной по высоте» и потребовать, чтобы длина пути до ближайшего пустого дочернего элемента находилась в пределах одного пути до самого дальнего пустого дочернего элемента. Мое определение менее строгое, и поэтому допускает больше деревьев.

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

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

Answer 2

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

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

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

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

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

В коде:

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

Полагаю, вы могли бы сделать это без использования шаблона Observer, но мне проще рассуждать таким образом.

---

[РЕДАКТИРОВАТЬ]: Почему вы не можете просто взять высоту каждой стороны. Посмотрите на это дерево:

        /\
       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   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. Вам нужна минимаксная спецификация (хотя фактический алгоритм может быть менее сложным, поскольку должно быть только две разрешенные высоты).

Answer 3

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

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     

Answer 4

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

Answer 5

Пост-решение заказа, пройдитесь по дереву только один раз. Временная сложность O (n), пробел O (1), это лучше, чем нисходящее решение. Я даю вам реализацию Java-версии.

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;
}

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

    if(Math.abs(left - right) > 1){
        return -1;
    }else{
        return 1 + Math.max(left, right);
    }
}

Answer 6

Определение сбалансированного по высоте бинарного дерева:

Двоичное дерево, в котором высота два поддерева каждого узла никогда отличаются более чем на 1.

Итак, Пустое двоичное дерево всегда сбалансировано по высоте.
Непустое двоичное дерево сбалансировано по высоте, если:

1. Его левое поддерево сбалансировано по высоте.
2. Правое поддерево сбалансировано по высоте.
3. Разница высот левое и правое поддерево не больше чем 1.

Рассмотрим дерево:

    A
     \ 
      B
     / \
    C   D

Как видно, левое поддерево A сбалансировано по высоте (так как оно пустое), как и его правое поддерево. Но все же дерево не сбалансировано по высоте, поскольку условие 3 не выполняется, так как высота левого поддерева равна 0, а высота правого поддерева 2.

Также следующее дерево не сбалансировано по высоте, хотя высота левого и правого поддерева одинакова. Ваш существующий код вернет true для него.

       A
     /  \ 
    B    C
   /      \
  D        G
 /          \
E            H

Так что слово каждые в определении очень важно.

Это будет работать:

int height(treeNodePtr root) {
        return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}

bool isHeightBalanced(treeNodePtr root) {
        return (root == NULL) ||
                (isHeightBalanced(root->left) &&
                isHeightBalanced(root->right) &&
                abs(height(root->left) - height(root->right)) <=1);
}

Ideone Link

Answer 7

Если двоичное дерево сбалансировано или не может быть проверено с помощью обхода уровня:

private boolean isLeaf(TreeNode root) {
    if (root.left == null && root.right == null)
        return true;
    return false;
}

private boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    Vector<TreeNode> queue = new Vector<TreeNode>();
    int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
    queue.add(root);
    while (!queue.isEmpty()) {
        int elementCount = queue.size();
        while (elementCount > 0) {
            TreeNode node = queue.remove(0);
            if (isLeaf(node)) {
                if (minLevel > level)
                    minLevel = level;
                if (maxLevel < level)
                    maxLevel = level;
            } else {
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            elementCount--;
        }
        if (abs(maxLevel - minLevel) > 1) {
            return false;
        }
        level++;
    }

    return true;
}

Answer 8

Это делается намного сложнее, чем на самом деле.

Алгоритм выглядит следующим образом:

1. Пусть A = глубина узла самого высокого уровня

2. Пусть B = глубина узла самого низкого уровня

3. Если abs (A-B) <= 1, то дерево сбалансировано </p>

Answer 9

То, что сбалансировано, немного зависит от имеющейся структуры. Например, B-дерево не может иметь узлы больше, чем определенная глубина от корня, или меньше в этом отношении, все данные живут на фиксированной глубине от корня, но это может быть несбалансированным, если распределение листьев к листьям -Но-один узел неровный. Пропускные списки Не имеют никакого представления о балансе, полагаясь вместо этого на вероятность достижения достойной производительности. Деревья Фибоначчи целенаправленно выходят из равновесия, откладывая перебалансировку для достижения превосходной асимптотической производительности в обмен на иногда более длинные обновления. AVL и красно-черные деревья прикрепляют метаданные к каждому узлу для достижения инварианта баланса глубины.

Все эти и другие структуры присутствуют в стандартных библиотеках большинства распространенных систем программирования (кроме python, RAGE!). Внедрение одного или двух является хорошей практикой программирования, но, вероятно, нецелесообразно тратить время на подготовку собственного к производству, если ваша проблема не имеет какой-то особенной производительности, которая не должна удовлетворяться какими-либо готовыми коллекциями.

Answer 10

Примечание 1: Высота любого поддерева вычисляется только один раз.

Примечание 2: Если левое поддерево не сбалансировано, вычисление правого поддерева, потенциально содержащего миллион элементов, пропускается.

// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
    if( tn ) {
        int const lh = maxHeight( tn->left );
        if( lh == -1 ) return -1;
        int const rh = maxHeight( tn->right );
        if( rh == -1 ) return -1;
        if( abs( lh - rh ) > 1 ) return -1;
        return 1 + max( lh, rh );
    }
    return 0;
}

bool isBalanced( TreeNode const * root ) {
    // Unless the maxHeight is -1, the subtree under "root" is balanced
    return maxHeight( root ) != -1;
}