Como determinar se a árvore binária está balanceada?

113

Já faz um tempo desde aqueles anos escolares. Consegui um emprego como especialista em TI em um hospital. Tentando fazer alguma programação real agora. Estou trabalhando em árvores binárias agora e gostaria de saber qual seria a melhor maneira de determinar se a árvore tem equilíbrio de altura.

Eu estava pensando em algo sobre isso:

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

Esta é uma boa implementação? Ou eu estou esquecendo de alguma coisa?

user69514
fonte
Se você gostaria de ver a árvore binária ascii de Donal Fellows com um gráfico: i.imgur.com/97C27Ek.png
user7643681
1
Boa resposta, me ajudou a entrar nos EUA. (piadas)
Henry

Respostas:

165

Tropecei nesta velha questão enquanto procurava por outra coisa. Percebi que você nunca obteve uma resposta completa.

A maneira de resolver esse problema é começar escrevendo uma especificação para a função que você está tentando escrever.

Especificação: Uma árvore binária bem formada é considerada "balanceada em altura" se (1) estiver vazia, ou (2) seus filhos esquerdo e direito estiverem balanceados em altura e a altura da árvore esquerda estiver dentro de 1 do altura da árvore certa.

Agora que você tem a especificação, o código é fácil de escrever. Basta seguir as especificações:

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

Traduzir isso para a linguagem de programação de sua escolha deve ser trivial.

Exercício bônus : este esboço de código ingênuo atravessa a árvore muitas vezes ao calcular as alturas. Você pode torná-lo mais eficiente?

Exercício de super bônus : suponha que a árvore esteja extremamente desequilibrada. Tipo, um milhão de nós de profundidade de um lado e três de profundidade do outro. Existe um cenário em que este algoritmo explode a pilha? Você pode consertar a implementação para que ela nunca estrague a pilha, mesmo quando dada uma árvore extremamente desequilibrada?

ATUALIZAÇÃO : Donal Fellows aponta em sua resposta que existem diferentes definições de 'equilibrado' que se pode escolher. Por exemplo, pode-se tomar uma definição mais estrita de "altura equilibrada" e exigir que o comprimento do caminho até a criança vazia mais próxima esteja dentro de um do caminho até a criança vazia mais distante . Minha definição é menos rígida do que essa e, portanto, admite mais árvores.

Alguém também pode ser menos rígido do que minha definição; pode-se dizer que uma árvore balanceada é aquela em que o comprimento máximo do caminho para uma árvore vazia em cada galho difere em não mais do que dois, ou três, ou alguma outra constante. Ou que o comprimento máximo do caminho é uma fração do comprimento mínimo do caminho, como metade ou um quarto.

Geralmente não importa. O objetivo de qualquer algoritmo de balanceamento de árvore é garantir que você não acabe na situação em que tenha um milhão de nós de um lado e três do outro. A definição de Donal é boa em teoria, mas na prática é uma dor chegar com um algoritmo de balanceamento de árvore que atenda a esse nível de rigidez. A economia de desempenho geralmente não justifica o custo de implementação. Você gasta muito tempo fazendo rearranjos desnecessários de árvores para atingir um nível de equilíbrio que na prática faz pouca diferença. Quem se importa se às vezes são necessários quarenta galhos para chegar à folha mais distante em uma árvore de um milhão de nós mal balanceada quando, em teoria, seriam necessários apenas vinte em uma árvore perfeitamente balanceada? A questão é que nunca leva um milhão. Passar do pior caso de um milhão para o pior caso de quarenta geralmente é suficiente; você não precisa ir até o caso ideal.

Eric Lippert
fonte
19
+1 para a única resposta correta, não acredito que ninguém foi capaz de responder isso por 8 meses ...
BlueRaja - Danny Pflughoeft
1
Resposta aos "exercícios" abaixo…
Potatoswatter
Exercício de bônus respondido abaixo.
Brian
A resposta do sdk abaixo parece estar certa e faz apenas 2 travessias de árvore, então é O (n). A menos que eu esteja perdendo alguma coisa, isso não resolve pelo menos sua primeira pergunta bônus. Você também pode usar a programação dinâmica e sua solução para armazenar em cache alturas intermediárias
Aly
Teoricamente, eu ainda teria que concordar com a definição de Donal Fellows.
Dhruv Gairola
26

O equilíbrio é uma propriedade realmente sutil; você acha que sabe o que é, mas é tão fácil errar. Em particular, até a resposta (boa) de Eric Lippert está errada. Isso porque a noção de altura não basta. Você precisa ter o conceito de alturas mínimas e máximas de uma árvore (onde a altura mínima é o menor número de passos da raiz à folha, e o máximo é ... bem, você entendeu). Dado isso, podemos definir o equilíbrio como:

Uma árvore onde a altura máxima de qualquer galho não é mais do que um a mais do que a altura mínima de qualquer galho.

(Na verdade, isso implica que os ramos estão equilibrados; você pode escolher o mesmo ramo para máximo e mínimo.)

Tudo o que você precisa fazer para verificar essa propriedade é uma simples travessia da árvore mantendo o controle da profundidade atual. A primeira vez que você volta atrás, isso lhe dá uma profundidade de linha de base. Cada vez depois disso, quando você voltar atrás, você compara a nova profundidade com a linha de base

  • se for igual à linha de base, você simplesmente continua
  • se for mais de um diferente, a árvore não está equilibrada
  • se for um, agora você conhece a faixa de equilíbrio e todas as profundidades subsequentes (quando você está prestes a retroceder) devem ser o primeiro ou o segundo valor.

Em código:

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

Suponho que você possa fazer isso sem usar o padrão Observer, mas acho mais fácil raciocinar dessa forma.


[EDIT]: Por que você não pode simplesmente medir a altura de cada lado. Considere esta árvore:

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

OK, um confuso pouco, mas cada lado da raiz é equilibrado: Cé profundidade 2, A, B, D, Eestão profundidade 3, e F, G, H, Jestão profundidade 4. A altura do ramo esquerdo é 2 (lembre-se a altura diminui à medida que atravessa o galho), a altura do galho direito é 3. No entanto, a árvore em geral não está equilibrada, pois há uma diferença de altura de 2 entre Ce F. Você precisa de uma especificação minimax (embora o algoritmo real possa ser menos complexo, pois deve haver apenas duas alturas permitidas).

Donal Fellows
fonte
Ah, bom ponto. Você poderia ter uma árvore que é h (LL) = 4, h (LR) = 3, h (RL) = 3, h (RR) = 2. Assim, h (L) = 4 eh (R) = 3, de modo que pareceria equilibrado para o algoritmo anterior, mas com uma profundidade máx. / Mínima de 4/2, isso não é equilibrado. Isso provavelmente faria mais sentido com uma imagem.
Tim,
1
Isso é o que acabei de adicionar (com a árvore gráfica ASCII mais desagradável do mundo).
Donal Fellows
@DonalFellows: você mencionou que a altura do ramo esquerdo é 2. mas o ramo esquerdo tem 4 nós incluindo a raiz e a folha A. A altura será 3 neste caso correto
tempestade cerebral
22

Isso apenas determina se o nível superior da árvore está equilibrado. Ou seja, você poderia ter uma árvore com dois longos galhos na extrema esquerda e na extrema direita, sem nada no meio, e isso retornaria verdadeiro. Você precisa verificar recursivamente root.lefte root.rightpara ver se eles estão balanceados internamente antes de retornar true.

Jesse Rusak
fonte
No entanto, se o código tivesse um método de altura máxima e mínima, se fosse balanceado globalmente, também seria balanceado localmente.
Ari
22

Resposta do exercício bônus. A solução simples. Obviamente, em uma implementação real, pode-se envolver isso ou algo assim para evitar que o usuário inclua altura em sua resposta.

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     
Brian
fonte
Se a árvore for maior do que algumas centenas de camadas de altura, você obterá uma exceção stackoverflow. Você fez isso com eficiência, mas não lida com conjuntos de dados de tamanho médio ou grande.
Eric Leschinski
É esse pseudocódigo que você acabou de criar ou é uma linguagem real? (Quero dizer a out heightnotação de variável " ")
kap
@kap: Este é um pseudocódigo, mas a sintaxe de saída é tirada do C #. Basicamente, significa que o parâmetro viaja da função chamada para o chamador (ao contrário dos parâmetros padrão, que viajam do chamador para a função chamada ou parâmetros ref, que viajam do chamador para a função chamada e vice-versa). Isso efetivamente permite que as funções retornem mais de um valor.
Brian de
20

Solução de pós-pedido, atravesse a árvore apenas uma vez. A complexidade do tempo é O (n), o espaço é O (1), é melhor do que a solução de cima para baixo. Eu te dou uma implementação da versão 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);
    }
}
Jiaji Li
fonte
4
boa solução, mas a complexidade do espaço deve ser O (H) onde H é a altura da árvore. Isso ocorre porque a alocação de pilha para recursão.
Legrass de
O que isso left == -1significa? Quando seria esse o caso? Presumimos que a chamada recursiva implica que isso left == -1é verdadeiro se todas as subárvores dos filhos à esquerda estiverem desequilibradas?
Aspen
left == 1significa que a subárvore esquerda está desequilibrada, então a árvore inteira está desequilibrada. Não precisamos mais verificar a subárvore certa e podemos retornar -1.
tning
A complexidade do tempo é O (n) porque você tem que passar por todos os elementos. E, se você tivesse x nós e levará y tempo para verificar o equilíbrio; se você tiver 2x nós, levará 2 anos para verificar o saldo. Tudo isso parece certo?
Jack
A explicação do desenho está aqui: algoritmos.tutorialhorizon.com/…
Shir
15

A definição de uma árvore binária de altura balanceada é:

Árvore binária em que a altura das duas subárvores de cada nó nunca difere em mais de 1.

Portanto, uma árvore binária vazia é sempre equilibrada em altura.
Uma árvore binária não vazia tem equilíbrio de altura se:

  1. Sua subárvore esquerda é equilibrada em altura.
  2. Sua subárvore direita é equilibrada em altura.
  3. A diferença entre as alturas da subárvore esquerda e direita não é maior que 1.

Considere a árvore:

    A
     \ 
      B
     / \
    C   D

Como visto, a subárvore esquerda de Aé equilibrada em altura (pois está vazia) e também sua subárvore direita. Mas ainda assim a árvore não está equilibrada em altura, pois a condição 3 não é atendida como a altura da subárvore esquerda 0e a altura da subárvore direita 2.

Além disso, a árvore a seguir não está equilibrada em altura, embora as alturas das subárvores esquerda e direita sejam iguais. Seu código existente retornará verdadeiro para ele.

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

Portanto, a palavra cada na definição é muito importante.

Isso vai funcionar:

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

Link Ideone

codadicto
fonte
Então essa resposta me ajudou muito. No entanto, achei que o [curso de introdução de algoritmos do MIT] gratuito parece contradizer a condição 3. A página 4 mostra uma árvore RB onde a altura do branch esquerdo é 2 e o branch direito é 4. Você pode me oferecer alguns esclarecimentos? Talvez eu não entenda a definição de uma subárvore. [1]: ocw.mit.edu/courses/electrical-engineering-and-computer-science/…
i8abug
A diferença parece vir dessa definição nas notas do curso. Todos os caminhos simples de qualquer nó x para uma folha descendente têm o mesmo número de nós pretos = black-height (x)
i8abug
Apenas para acompanhar, encontrei uma definição que muda o ponto (3) em sua resposta para "cada folha está 'não mais do que uma certa distância' da raiz do que qualquer outra folha". Isso parece satisfazer ambos os casos. Aqui está o link de algum software de curso aleatório
i8abug
8

Se a árvore binária está balanceada ou não, pode ser verificada pela passagem de ordem de nível:

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;
}
por sorte
fonte
1
Excelente resposta. Acho que atende a todos os requisitos que Eric postou com relação a Bônus e Super Bônus. É iterativo (usando uma fila) e não recursivo - portanto, a pilha de chamadas não será estourada e movemos todos os problemas de memória para o heap. Nem mesmo requer atravessar a árvore inteira. Ele se move nível por nível, portanto, se uma árvore estiver totalmente desequilibrada para um lado, ela o encontrará muito em breve (mais cedo? Bem mais cedo do que a maioria dos algoritmos recursivos, embora você possa implementar um algoritmo iterativo de travessia pós-pedido que encontrará o último nível desequilibra mais cedo, mas agirá de forma mais pobre nos primeiros níveis). Então, +1 :-)
David Refaeli,
7

Isso está se tornando muito mais complicado do que realmente é.

O algoritmo é o seguinte:

  1. Seja A = profundidade do nó de nível mais alto
  2. Seja B = profundidade do nó de nível mais baixo

  3. Se abs (AB) <= 1, então a árvore está equilibrada

Mike
fonte
Simples e direto!
Wasim Thabraze
3
Dois problemas, não é tão eficiente quanto poderia ser, você está fazendo duas passagens sobre a árvore inteira. E para árvores que têm um nó à esquerda e milhares à direita, você passa desnecessariamente por tudo, quando poderia ter parado após 3 verificações.
Eric Leschinski
5

O que significa equilibrado depende um pouco da estrutura em questão. Por exemplo, A B-Tree não pode ter nós mais do que uma certa profundidade da raiz, ou menos, todos os dados vivem em uma profundidade fixa da raiz, mas pode estar desequilibrado se a distribuição de folhas para folhas -mas-um nó é irregular. Listas de omissão Não tenha nenhuma noção de equilíbrio, confiando, em vez disso, na probabilidade de alcançar um desempenho decente. Árvores Fibonacci propositalmente caem fora de equilíbrio, adiando o reequilíbrio para alcançar desempenho assintótico superior em troca de atualizações ocasionalmente mais longas. Árvores AVL e Red-Black anexam metadados a cada nó para atingir um invariante de equilíbrio de profundidade.

Todas essas estruturas e mais estão presentes nas bibliotecas padrão dos sistemas de programação mais comuns (exceto python, RAGE!). Implementar um ou dois é uma boa prática de programação, mas provavelmente não é um bom uso de tempo para lançar o seu próprio para produção, a menos que seu problema tenha algum desempenho peculiar que não precise ser satisfeito por nenhuma coleção pronta para uso.

SingleNegationElimination
fonte
4

Nota 1: A altura de qualquer subárvore é calculada apenas uma vez.

Nota 2: Se a subárvore esquerda estiver desequilibrada, o cálculo da subárvore direita, potencialmente contendo milhões de elementos, é ignorado.

// 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;
}
Uma corrida
fonte
3

O equilíbrio geralmente depende do comprimento do caminho mais longo em cada direção. O algoritmo acima não fará isso por você.

O que você está tentando implementar? Existem árvores de equilíbrio automático ao redor (AVL / Red-black). Na verdade, as árvores Java são equilibradas.

Uri
fonte
3

Se for para o seu trabalho , sugiro:

  1. não reinvente a roda e
  2. use / compre COTS em vez de brincar com bits.
  3. Economize seu tempo / energia para resolver problemas de negócios.
Steven A. Lowe
fonte
3
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));
}
sdk
fonte
Acho que essa solução não é correta. Se você passar uma árvore que tem um único nó, ou seja, uma raiz ela retornará como maxDepth 1(o mesmo para minDepth). A profundidade correta, porém, deve ser 0. A raiz de uma árvore sempre tem 0profundidade
Crátilo
3

Aqui está uma solução testada e trabalhada completa em C # (desculpe, não sou dev java) (basta copiar e colar no aplicativo de console). Eu sei que a definição de balanceado varia, então nem todos podem gostar dos resultados do meu teste, mas por favor, basta olhar para a abordagem ligeiramente diferente de verificar a profundidade / altura em um loop recursivo e sair na primeira incompatibilidade sem salvar a altura / nível / profundidade do nó em cada nó (apenas mantendo-o em uma chamada de função).

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);
            }
        }
    }
}
sbp
fonte
Não entendo como alguém pode votar negativamente nesta resposta 2 minutos após postar a resposta ?? O voto negativo é bom, mas você poderia explicar o que há de errado com essa solução?
sbp
2
#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;
}
Frank Raaj
fonte
você pode querer adicionar alguns comentários
jgauffin
2

RE: a solução de @ lucky usando um BFS para fazer uma travessia de ordem de nível.

Percorremos a árvore e mantemos uma referência a vars min / max-level que descreve o nível mínimo em que um nó é uma folha.

Eu acredito que a solução @lucky requer uma modificação. Como sugerido por @codaddict, em vez de verificar se um nó é uma folha, devemos verificar se O filho esquerdo ou direito é nulo (não ambos). Caso contrário, o algoritmo consideraria esta uma árvore balanceada válida:

     1
    / \
   2   4
    \   \
     3   1

Em 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

Esta solução deve satisfazer todas as estipulações fornecidas na questão inicial, operando em tempo O (n) e espaço O (n). O estouro de memória seria direcionado para o heap em vez de explodir uma pilha de chamadas recursiva.

Alternativamente, poderíamos percorrer inicialmente a árvore para computar + cache máximas alturas para cada subárvore raiz iterativamente. Em seguida, em outra execução iterativa, verifique se as alturas em cache das subárvores esquerda e direita de cada raiz nunca diferem em mais de um. Isso também seria executado no tempo O (n) e no espaço O (n), mas de forma iterativa para não causar estouro de pilha.

Vikasnair
fonte
1

Bem, você precisa encontrar uma maneira de determinar as alturas da esquerda e da direita e se a esquerda e a direita estão equilibradas.

E eu apenas return height(node->left) == height(node->right);

Quanto a escrever uma heightfunção, leia: Noções básicas sobre recursão

tpdi
fonte
3
Você deseja que as alturas esquerda e direita estejam dentro de 1, não necessariamente iguais.
Alex B
1

De que tipo de árvore você está falando? Existem árvores com equilíbrio próprio lá fora. Verifique seus algoritmos onde eles determinam se precisam reordenar a árvore para manter o equilíbrio.

lothar
fonte
1

Aqui está uma versão baseada em uma travessia de profundidade genérica. Deve ser mais rápido do que a outra resposta correta e lidar com todos os "desafios" mencionados. Desculpas pelo estilo, eu realmente não conheço Java.

Você ainda pode torná-lo muito mais rápido retornando mais cedo, se máximo e mínimo estiverem definidos e tiverem uma diferença> 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 );
}
Potatoswatter
fonte
1
Uma boa tentativa, mas claramente não funciona. Seja x um nó nulo. Deixe um nó de árvore não nulo ser denotado como (LEFT VALUE RIGHT). Considere a árvore (x A (x B x)). "root" aponta para os nós A, B, A, B, A, B ... para sempre. Quer tentar novamente? Uma dica: na verdade, é mais fácil sem dicas para os pais.
Eric Lippert
@Eric: Opa, consertado (eu acho). Bem, estou tentando fazer isso sem memória O (profundidade), e se a estrutura não tiver ponteiros pai (geralmente tem), você precisará usar uma pilha.
Potatoswatter
Portanto, o que você está me dizendo é que prefere usar a memória permanente O (n) em ponteiros pai para evitar a alocação de memória temporária O (d), onde log n <= d <= n? Isso parece uma falsa economia.
Eric Lippert
Infelizmente, embora você tenha corrigido o problema com a travessia, há um problema muito maior aqui. Isso não testa se uma árvore está balanceada, mas se uma árvore tem todas as suas folhas próximas ao mesmo nível. Essa não é a definição de "equilibrado" que dei. Considere a árvore ((((x D x) C x) B x) A x). Seu código relata que isso é "balanceado" quando obviamente está desequilibrado ao máximo. Quer tentar novamente?
Eric Lippert
Resposta de Eric 1: não é uma economia falsa se você já usa os ponteiros do pai para outra coisa. resposta 2: claro, por que não. Esta é uma maneira bizarra de depuração ... Eu não deveria estar escrevendo cegamente travessias de nada às 4 da manhã ...
Potatoswatter
1
/* 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;
    }
}
Intuiter
fonte
1
Você deve adicionar alguma descrição à sua resposta e / ou comentários ao seu exemplo de código.
Brad Campbell
1
class Node {
    int data;
    Node left;
    Node right;

    // assign variable with constructor
    public Node(int data) {
        this.data = data;
    }
}

public class BinaryTree {

    Node root;

    // get max depth
    public static int maxDepth(Node node) {
        if (node == null)
            return 0;

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

    // get min depth
    public static int minDepth(Node node) {
        if (node == null)
            return 0;

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

    // return max-min<=1 to check if tree balanced
    public boolean isBalanced(Node node) {

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

        return false;
    }

    public static void main(String... strings) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);


        if (tree.isBalanced(tree.root))
            System.out.println("Tree is balanced");
        else
            System.out.println("Tree is not balanced");
    }
}
Pranay
fonte
0

Aqui está o que eu tentei para o exercício bônus de Eric. Tento desenrolar meus loops recursivos e retornar assim que descobrir que uma subárvore não está equilibrada.

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
}
Sudharsanan
fonte
0
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;
    }
sempre
fonte
0

Uma árvore vazia é equilibrada em altura. Uma árvore binária não vazia T é balanceada se:

1) A subárvore esquerda de T é balanceada

2) A subárvore direita de T está equilibrada

3) A diferença entre as alturas da subárvore esquerda e da subárvore direita não é superior a 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;
}

Complexidade de tempo: O (n)

Saqlain
fonte
0

Para ter um melhor desempenho, especialmente em árvores enormes, você pode economizar a altura em cada nó, por isso é uma troca espaço x desempenho:

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

Exemplo de implementação da adição e mesmo para exclusão

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;

}
Maher Rezeq
fonte
-1
    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;
        }
    }
}
Saurabh
fonte
-2

Não funcionaria?

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

Qualquer árvore desequilibrada sempre falharia nisso.

Sumit Kishore
fonte
4
Muitas árvores equilibradas também falharão.
Brian