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

Ответ 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)

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

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

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

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

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

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

Ответ 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, но мне легче рассуждать таким образом.

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

Ответ 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     

Ответ 4

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

Ответ 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);
    }
}

Ответ 6

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

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

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

• Левое поддерево сбалансировано по высоте.
• Его правое поддерево сбалансировано по высоте.
• Разница между высотами левое и правое поддерево не больше чем 1.

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

    A
     \ 
      B
     / \
    C   D

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

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

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

Значит, слово каждый в def очень важно.

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

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

Идеальная ссылка

Ответ 7

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

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

• Пусть A = глубина наивысшего уровня node

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

• Если abs (A-B) <= 1, то дерево сбалансировано

Ответ 8

Если бинарное дерево сбалансировано или нет, можно проверить путем обхода порядка:

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

Ответ 9

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

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

Ответ 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;
}

Ответ 11

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

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

Ответ 12

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

• не изобретать велосипед и
• использовать/покупать COTS вместо возиться с битами.
• Экономия вашего времени/энергии для решения бизнес-задач.

Ответ 13

public boolean isBalanced(TreeNode root)
{
    return (maxDepth(root) - minDepth(root) <= 1);
}

public int maxDepth(TreeNode root)
{
    if (root == null) return 0;

    return 1 + max(maxDepth(root.left), maxDepth(root.right));
}

public int minDepth (TreeNode root)
{
    if (root == null) return 0;

    return 1 + min(minDepth(root.left), minDepth(root.right));
}

Ответ 14

Вот полное отработанное тестируемое решение на С# (извините, что я не java dev) (просто скопируйте вставку в консольном приложении). Я знаю, что определение сбалансированного варьируется, поэтому не всем может понравиться мой результат теста, но, пожалуйста, просто взгляните на немного другой подход проверки глубины/высоты в рекурсивном цикле и выхода из первого несоответствия без сохранения node высоты/уровня/глубины на каждый node (поддерживается только при вызове функции).

using System;
using System.Linq;
using System.Text;

namespace BalancedTree
{
    class Program
    {
        public static void Main()
        {
            //Value Gathering
            Console.WriteLine(RunTreeTests(new[] { 0 }));
            Console.WriteLine(RunTreeTests(new int[] { }));

            Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
            Console.WriteLine(RunTreeTests(null));
            Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
            Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));

            Console.ReadKey();
        }

        static string RunTreeTests(int[] scores)
        {
            if (scores == null || scores.Count() == 0)
            {
                return null;
            }

            var tree = new BinarySearchTree();

            foreach (var score in scores)
            {
                tree.InsertScore(score);
            }

            Console.WriteLine(tree.IsBalanced());

            var sb = tree.GetBreadthWardsTraversedNodes();

            return sb.ToString(0, sb.Length - 1);
        }
    }

    public class Node
    {
        public int Value { get; set; }
        public int Count { get; set; }
        public Node RightChild { get; set; }
        public Node LeftChild { get; set; }
        public Node(int value)
        {
            Value = value;
            Count = 1;
        }

        public override string ToString()
        {
            return Value + ":" + Count;
        }

        public bool IsLeafNode()
        {
            return LeftChild == null && RightChild == null;
        }

        public void AddValue(int value)
        {
            if (value == Value)
            {
                Count++;
            }
            else
            {
                if (value > Value)
                {
                    if (RightChild == null)
                    {
                        RightChild = new Node(value);
                    }
                    else
                    {
                        RightChild.AddValue(value);
                    }
                }
                else
                {
                    if (LeftChild == null)
                    {
                        LeftChild = new Node(value);
                    }
                    else
                    {
                        LeftChild.AddValue(value);
                    }
                }
            }
        }
    }

    public class BinarySearchTree
    {
        public Node Root { get; set; }

        public void InsertScore(int score)
        {
            if (Root == null)
            {
                Root = new Node(score);
            }
            else
            {
                Root.AddValue(score);
            }
        }

        private static int _heightCheck;
        public bool IsBalanced()
        {
            _heightCheck = 0;
            var height = 0;
            if (Root == null) return true;
            var result = CheckHeight(Root, ref height);
            height--;
            return (result && height == 0);
        }

        private static bool CheckHeight(Node node, ref int height)
        {
            height++;
            if (node.LeftChild == null)
            {
                if (node.RightChild != null) return false;
                if (_heightCheck != 0) return _heightCheck == height;
                _heightCheck = height;
                return true;
            }
            if (node.RightChild == null)
            {
                return false;
            }

            var leftCheck = CheckHeight(node.LeftChild, ref height);
            if (!leftCheck) return false;
            height--;
            var rightCheck = CheckHeight(node.RightChild, ref height);
            if (!rightCheck) return false;
            height--;
            return true;
        }


        public StringBuilder GetBreadthWardsTraversedNodes()
        {
            if (Root == null) return null;
            var traversQueue = new StringBuilder();
            traversQueue.Append(Root + ",");
            if (Root.IsLeafNode()) return traversQueue;
            TraversBreadthWards(traversQueue, Root);
            return traversQueue;
        }

        private static void TraversBreadthWards(StringBuilder sb, Node node)
        {
            if (node == null) return;
            sb.Append(node.LeftChild + ",");
            sb.Append(node.RightChild + ",");
            if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.LeftChild);
            }
            if (node.RightChild != null && !node.RightChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.RightChild);
            }
        }
    }
}

Ответ 15

#include <iostream>
#include <deque>
#include <queue>

struct node
{
    int data;
    node *left;
    node *right;
};

bool isBalanced(node *root)
{
    if ( !root)
    {
        return true;
    }

    std::queue<node *> q1;
    std::queue<int>  q2;
    int level = 0, last_level = -1, node_count = 0;

    q1.push(root);
    q2.push(level);

    while ( !q1.empty() )
    {
        node *current = q1.front();
        level = q2.front();

        q1.pop();
        q2.pop();

        if ( level )
        {
            ++node_count;
        }

                if ( current->left )
                {
                        q1.push(current->left);
                        q2.push(level + 1);
                }

                if ( current->right )
                {
                        q1.push(current->right);
                        q2.push(level + 1);
                }

        if ( level != last_level )
        {
            std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
            if ( level && (node_count - 1) != (1 << (level-1)) )
            {
                return false;
            }

            last_level = q2.front();
            if ( level ) node_count = 1;
        }
    }

    return true;
}

int main()
{
    node tree[15];

    tree[0].left  = &tree[1];
    tree[0].right = &tree[2];
    tree[1].left  = &tree[3];
    tree[1].right = &tree[4];
    tree[2].left  = &tree[5];
    tree[2].right = &tree[6];
    tree[3].left  = &tree[7];
    tree[3].right = &tree[8];
    tree[4].left  = &tree[9];   // NULL;
    tree[4].right = &tree[10];  // NULL;
    tree[5].left  = &tree[11];  // NULL;
    tree[5].right = &tree[12];  // NULL;
    tree[6].left  = &tree[13];
    tree[6].right = &tree[14];
    tree[7].left  = &tree[11];
    tree[7].right = &tree[12];
    tree[8].left  = NULL;
    tree[8].right = &tree[10];
    tree[9].left  = NULL;
    tree[9].right = &tree[10];
    tree[10].left = NULL;
    tree[10].right= NULL;
    tree[11].left = NULL;
    tree[11].right= NULL;
    tree[12].left = NULL;
    tree[12].right= NULL;
    tree[13].left = NULL;
    tree[13].right= NULL;
    tree[14].left = NULL;
    tree[14].right= NULL;

    std::cout << "Result: " << isBalanced(tree) << std::endl;

    return 0;
}

Ответ 16

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

И я просто return height(node->left) == height(node->right);

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

Ответ 17

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

Ответ 18

Вот версия, основанная на общем прохождении по глубине. Должен быть быстрее другого правильного ответа и обрабатывать все упомянутые "проблемы". Извинения за стиль, я действительно не знаю 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 );
}

Ответ 19

/* Returns true if Tree is balanced, i.e. if the difference between the longest path and the shortest path from the root to a leaf node is no more than than 1. This difference can be changed to any arbitrary positive number. */
boolean isBalanced(Node root) {
    if (longestPath(root) - shortestPath(root) > 1)
        return false;
    else
        return true;
}


int longestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = longestPath(root.left);
        int rightPathLength = longestPath(root.right);
        if (leftPathLength >= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

int shortestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = shortestPath(root.left);
        int rightPathLength = shortestPath(root.right);
        if (leftPathLength <= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

Ответ 20

RE: @удачное решение, использующее BFS для обхода уровня порядка.

Мы пересекаем дерево и сохраняем ссылку на переменные min/max-level, которые описывают минимальный уровень, на котором узел является листом.

Я считаю, что решение @Lucky требует модификации. Как подсказывает @codaddict, вместо того, чтобы проверять, является ли узел листом, мы должны проверить, является ли ЛИБО или правый потомок нулевым (а не оба). В противном случае алгоритм будет считать это допустимым сбалансированным деревом:

     1
    / \
   2   4
    \   \
     3   1

В Python:

def is_bal(root):
    if root is None:
        return True

    import queue

    Q = queue.Queue()
    Q.put(root)

    level = 0
    min_level, max_level = sys.maxsize, sys.minsize

    while not Q.empty():
        level_size = Q.qsize()

        for i in range(level_size):
            node = Q.get()

            if not node.left or node.right:
                min_level, max_level = min(min_level, level), max(max_level, level)

            if node.left:
                Q.put(node.left)
            if node.right:
                Q.put(node.right)

        level += 1

        if abs(max_level - min_level) > 1:
            return False

    return True

Это решение должно удовлетворять всем условиям, изложенным в исходном вопросе, работая в O (n) времени и O (n) пространстве. Переполнение памяти будет направлено на кучу, а не на рекурсивный стек вызовов.

В качестве альтернативы, мы могли бы сначала пройти по дереву, чтобы вычислять + кэшировать максимальные высоты для каждого корневого поддерева итеративно. Затем в другом итеративном прогоне проверьте, не отличается ли высота кэшированных левого и правого поддеревьев для каждого корня более чем на единицу. Это также будет выполняться во времени O (n) и в пространстве O (n), но итеративно, чтобы не вызывать переполнение стека.

Ответ 21

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

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
}

Ответ 22

public int height(Node node){
    if(node==null)return 0;
    else{
        int l=height(node.leftChild);
        int r=height(node.rightChild);
       return(l>r?l+1:r+1);

}}
public boolean balanced(Node n){

    int l= height(n.leftChild);
    int r= height(n.rightChild);

    System.out.println(l + " " +r);
    if(Math.abs(l-r)>1)
        return false;
    else 
        return true;
    }

Ответ 23

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

1) Левое поддерево T сбалансировано

2) Правое поддерево T сбалансировано

3) Разница между высотами левого поддерева и правым поддеревом не более 1.

/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
  int data;
  struct node* left;
  struct node* right;
};

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
     return 1;
  }

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);
  r = isBalanced(root->right,&rh);

  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;
}


/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

int main()
{
  int height = 0;

  /* Constructed binary tree is
             1
           /   \
         2      3
       /  \    /
     4     5  6
    /
   7
  */   
  struct node *root = newNode(1);  
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);
  root->left->left->left = newNode(7);

  if(isBalanced(root, &height))
    printf("Tree is balanced");
  else
    printf("Tree is not balanced");    

  getchar();
  return 0;
}

Сложность времени: O (n)

Ответ 24

Чтобы иметь лучшую производительность, особенно на огромных деревьях, вы можете сохранить высоту в каждом node, так что это компромиссное пространство Vs:

class Node {
    Node left;
    Node right;
    int value;
    int height;
}

Пример реализации добавления и того же для удаления

void addNode(Node root,int v)
{    int height =0;
     while(root != null)
     {
         // Since we are adding new node so the height 
         // will increase by one in each node we will pass by
         root.height += 1;
         height++;
         else if(v > root.value){
            root = root.left();
            }
         else{
         root = root.right();
         }

     }

         height++;
         Node n = new Node(v , height);
         root = n;         
}
int treeMaxHeight(Node root)
{
 return Math.Max(root.left.height,root.right.height);
}

int treeMinHeight(Node root)
{
 return Math.Min(root.left.height,root.right.height);

}

Boolean isNodeBlanced(Node root)
{
   if (treeMaxHeight(root) - treeMinHeight(root) > 2)
       return false;

  return true;
}

Boolean isTreeBlanced (Node root)
{
    if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
    return true;

  return false;

}

Ответ 25

Класс Node {int data; Node left; Узел оставлен; Node right; Узел правый;

//assign variable with constructor public Node(int data) { this.data = data;//присваиваем переменную с помощью конструктора public Node (int data) {this.data = data; } } }}

открытый класс BinaryTree {

Корень узла;

//получить максимальную глубину public static int maxDepth (Node node) {if (node == null) return 0;

  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));     }

  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));     }

//get min depth public static int minDepth(Node node) { if (node == null) return 0;//получаем минимальную глубину public static int minDepth (Node node) {if (node == null) return 0;

  return 1 + Math.min(minDepth(node.left), minDepth(node.right));     }

  return 1 + Math.min(minDepth(node.left), minDepth(node.right));     }

//return max-min<=1 to check if tree balanced public boolean isBalanced(Node node) {//возвращаем max-min <= 1, чтобы проверить, сбалансировано ли дерево public boolean isBalanced (Node node) {

  if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)             return true;

  return false;   }

  if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)             return true;

  return false;   }

public static void main(String... strings) { BinaryTree tree = new BinaryTree(); public static void main (String... strings) {BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root = новый узел (1); tree.root.left = new Node(2); tree.root.left = new Node (2); tree.root.right = new Node(3); tree.root.right = новый узел (3);

  if (tree.isBalanced(tree.root))             System.out.println("Tree is

  if (tree.isBalanced(tree.root))             System.out.println("Tree is

balanced"); else System.out.println("Tree is not balanced"); } } сбалансированный "); еще System.out.println(" Дерево не сбалансировано ");}}

Ответ 26

    static boolean isBalanced(Node root) {
    //check in the depth of left and right subtree
    int diff = depth(root.getLeft()) - depth(root.getRight());
    if (diff < 0) {
        diff = diff * -1;
    }
    if (diff > 1) {
        return false;
    }
    //go to child nodes
    else {
        if (root.getLeft() == null && root.getRight() == null) {
            return true;
        } else if (root.getLeft() == null) {
            if (depth(root.getRight()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getRight() == null) {
            if (depth(root.getLeft()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
            return true;
        } else {
            return false;
        }
    }
}

Ответ 27

Не работает ли это?

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

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