¿Cómo determinar si el árbol binario está equilibrado?

113

Ha pasado un tiempo desde esos años escolares. Conseguí un trabajo como especialista en informática en un hospital. Tratando de moverme para hacer una programación real ahora. Ahora estoy trabajando en árboles binarios y me preguntaba cuál sería la mejor manera de determinar si el árbol está equilibrado en altura.

Estaba pensando en algo a lo largo de esto:

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

¿Es esta una buena implementación? ¿O me estoy perdiendo algo?

user69514
fuente
Si desea ver el árbol binario ascii de Donal Fellows con un gráfico: i.imgur.com/97C27Ek.png
user7643681
1
Buena respuesta, me ayudó a ingresar a los Estados Unidos. (bromas)
Henry

Respuestas:

165

Me encontré con esta vieja pregunta mientras buscaba algo más. Noto que nunca obtuvo una respuesta completa.

La forma de resolver este problema es comenzar escribiendo una especificación para la función que está intentando escribir.

Especificación: Se dice que un árbol binario bien formado tiene "altura equilibrada" si (1) está vacío, o (2) sus elementos secundarios izquierdo y derecho están equilibrados en altura y la altura del árbol de la izquierda está dentro de 1 del altura del árbol de la derecha.

Ahora que tiene la especificación, el código es trivial de escribir. Simplemente siga las especificaciones:

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

Traducir eso al lenguaje de programación de su elección debería ser trivial.

Ejercicio adicional : este boceto de código ingenuo atraviesa el árbol demasiadas veces al calcular las alturas. ¿Puedes hacerlo más eficiente?

Ejercicio de súper bonificación : supongamos que el árbol está enormemente desequilibrado. Como, un millón de nodos de profundidad en un lado y tres de profundidad en el otro. ¿Existe un escenario en el que este algoritmo arruine la pila? ¿Puede arreglar la implementación para que nunca arruine la pila, incluso cuando se le da un árbol enormemente desequilibrado?

ACTUALIZACIÓN : Donal Fellows señala en su respuesta que existen diferentes definiciones de "equilibrado" que se pueden elegir. Por ejemplo, se podría tomar una definición más estricta de "altura equilibrada", y requerir que la longitud del camino al niño vacío más cercano esté dentro de uno de los caminos al niño vacío más lejano . Mi definición es menos estricta que eso y, por lo tanto, admite más árboles.

También se puede ser menos estricto que mi definición; se podría decir que un árbol equilibrado es aquel en el que la longitud máxima del camino a un árbol vacío en cada rama no difiere en más de dos, tres o alguna otra constante. O que la longitud máxima de la ruta es una fracción de la longitud mínima de la ruta, como la mitad o un cuarto.

Realmente no importa por lo general. El objetivo de cualquier algoritmo de equilibrio de árboles es garantizar que no termines en la situación en la que tienes un millón de nodos en un lado y tres en el otro. La definición de Donal está bien en teoría, pero en la práctica es un fastidio crear un algoritmo de equilibrio de árboles que cumpla con ese nivel de rigor. Los ahorros de rendimiento generalmente no justifican el costo de implementación. Pasas mucho tiempo haciendo reordenamientos innecesarios de los árboles para lograr un nivel de equilibrio que en la práctica hace poca diferencia. ¿A quién le importa si a veces se necesitan cuarenta ramas para llegar a la hoja más lejana de un árbol con un equilibrio imperfecto de un millón de nodos cuando, en teoría, sólo podrían tomar veinte en un árbol perfectamente equilibrado? El caso es que nunca se necesita un millón. Pasar del peor de los casos de un millón al peor de los cuarenta suele ser suficiente; no tiene que ir hasta el caso óptimo.

Eric Lippert
fuente
19
+1 por la única respuesta correcta, no puedo creer que nadie haya podido responder esto durante 8 meses ...
BlueRaja - Danny Pflughoeft
1
Responda a los "ejercicios" a continuación ...
Potatoswatter
Ejercicio de bonificación respondido a continuación.
Brian
La respuesta de sdk a continuación parece ser correcta y solo hace 2 recorridos de árboles, por lo que O (n). A menos que me falte algo, eso no resuelve al menos su primera pregunta adicional. Por supuesto, también puede utilizar la programación dinámica y su solución para almacenar en caché alturas intermedias
Aly
En teoría, todavía tendría que estar del lado de la definición de Donal Fellows.
Dhruv Gairola
26

El equilibrio es una propiedad verdaderamente sutil; cree que sabe lo que es, pero es muy fácil equivocarse. En particular, incluso la (buena) respuesta de Eric Lippert es incorrecta. Eso es porque la noción de altura no es suficiente. Necesitas tener el concepto de alturas mínimas y máximas de un árbol (donde la altura mínima es el menor número de pasos desde la raíz hasta una hoja, y el máximo es ... bueno, te haces una idea). Dado eso, podemos definir el equilibrio como:

Un árbol donde la altura máxima de cualquier rama no es más de uno más que la altura mínima de cualquier rama.

(En realidad, esto implica que las ramas están equilibradas; puede elegir la misma rama tanto para el máximo como para el mínimo).

Todo lo que necesita hacer para verificar esta propiedad es un simple recorrido de árbol que realiza un seguimiento de la profundidad actual. La primera vez que retrocede, eso le da una profundidad de referencia. Cada vez que retrocede, compara la nueva profundidad con la línea de base

  • si es igual a la línea de base, entonces continúe
  • si es más de uno diferente, el árbol no está equilibrado
  • si es único, ahora conoce el rango para el equilibrio, y todas las profundidades posteriores (cuando esté a punto de retroceder) deben ser el primer o el segundo valor.

En codigo:

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

Supongo que podrías hacer esto sin usar el patrón Observer, pero me resulta más fácil razonar de esta manera.


[EDITAR]: Por qué no puedes simplemente tomar la altura de cada lado. Considere este árbol:

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

OK, un desordenado poco, pero cada lado de la raíz es equilibrado: Ces la profundidad 2, A, B, D, Eson la profundidad de 3, y F, G, H, Json la profundidad 4. La altura de la rama izquierda es 2 (recuerde la altura disminuye a medida que atraviesan la rama), la altura de la rama derecha es 3. Sin embargo, el árbol en general no está equilibrado ya que hay una diferencia de altura de 2 entre Cy F. Necesita una especificación minimax (aunque el algoritmo real puede ser menos complejo, ya que solo debería haber dos alturas permitidas).

Becarios Donal
fuente
Ah, buen punto. Podría tener un árbol que sea h (LL) = 4, h (LR) = 3, h (RL) = 3, h (RR) = 2. Por lo tanto, h (L) = 4 y h (R) = 3, por lo que parecería equilibrado con el algoritmo anterior, pero con una profundidad máxima / mínima de 4/2, esto no está equilibrado. Esto probablemente tendría más sentido con una imagen.
Tim
1
Eso es lo que acabo de agregar (con el árbol gráfico ASCII más desagradable del mundo).
Donal Fellows
@DonalFellows: mencionaste que la altura de la rama izquierda es 2. pero la rama izquierda tiene 4 nodos, incluida la raíz y la hoja A. La altura será 3 en este caso correcta
tormenta de
22

Esto solo determina si el nivel superior del árbol está equilibrado. Es decir, podría tener un árbol con dos ramas largas en el extremo izquierdo y el extremo derecho, sin nada en el medio, y esto volvería a ser cierto. Debe comprobar de forma recursiva los root.lefty root.rightpara ver si también están equilibrados internamente antes de volver a verdadero.

Jesse Rusak
fuente
Sin embargo, si el código tuviera un método de altura máxima y mínima, si está equilibrado globalmente, también estaría equilibrado localmente.
Ari
22

Respuesta adicional al ejercicio. La solución simple. Obviamente, en una implementación real, uno podría ajustar esto o algo para evitar que el usuario incluya la altura en su respuesta.

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
fuente
Si el árbol tiene más de unos pocos cientos de capas de altura, obtendrá una excepción de desbordamiento de pila. Lo ha hecho de manera eficiente, pero no maneja conjuntos de datos de tamaño mediano o grande.
Eric Leschinski
¿Es este pseudocódigo que se te ocurrió o es un lenguaje real? (Me refiero a la out heightnotación variable " ")
kap
@kap: este es un pseudocódigo, pero la sintaxis de salida se toma de C #. Básicamente, significa que el parámetro viaja desde la función llamada a la función llamada (a diferencia de los parámetros estándar, que viajan desde la persona que llama a la función llamada o parámetros de referencia, que viajan desde la persona que llama a la función llamada y viceversa). Esto efectivamente permite que las funciones devuelvan más de un valor.
Brian
20

Solución posterior al pedido, atraviesa el árbol solo una vez. La complejidad del tiempo es O (n), el espacio es O (1), es mejor que la solución de arriba hacia abajo. Te doy una implementación de la versión 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
fuente
4
buena solución, pero la complejidad del espacio debería ser O (H) donde H es la altura del árbol. Esto se debe a la asignación de pila para la recursividad.
legrass
¿Qué left == -1significa? ¿Cuándo sería ese el caso? ¿Asumimos que la llamada recursiva implica que left == -1es verdadera si todos los subárboles de los hijos de la izquierda están desequilibrados?
Aspen
left == 1significa que el subárbol izquierdo está desequilibrado, entonces todo el árbol está desequilibrado. Ya no tenemos que comprobar el subárbol derecho y podemos volver-1 .
2016
La complejidad del tiempo es O (n) porque tienes que pasar por todos los elementos. Y, si tenía x nodos y se necesitará y tiempo para verificar el saldo; si tenía 2 nodos, le tomará 2 años verificar el saldo. ¿Todo eso suena bien?
Jack
Explicación bien con el dibujo está aquí: algorithms.tutorialhorizon.com/...
Shir
15

La definición de un árbol binario de altura equilibrada es:

Árbol binario en el que la altura de los dos subárboles de cada nodo nunca difiere en más de 1.

Entonces, un árbol binario vacío siempre está equilibrado en altura.
Un árbol binario no vacío está equilibrado en altura si:

  1. Su subárbol izquierdo está equilibrado en altura.
  2. Su subárbol derecho está equilibrado en altura.
  3. La diferencia entre las alturas del subárbol izquierdo y derecho no es mayor que 1.

Considere el árbol:

    A
     \ 
      B
     / \
    C   D

Como se ve, el subárbol izquierdo de Aestá equilibrado en altura (ya que está vacío) y también su subárbol derecho. Pero aún así, el árbol no está equilibrado en altura, ya que no se cumple la condición 3, ya que la altura del subárbol izquierdo es 0y la altura del subárbol derecho 2.

Además, el siguiente árbol no está equilibrado en altura a pesar de que la altura del subárbol izquierdo y derecho son iguales. Su código existente devolverá verdadero para él.

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

Así que la palabra todos en la definición es muy importante.

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

Enlace ideone

codaddict
fuente
Entonces esta respuesta me ayudó mucho. Sin embargo, encontré que el [curso de introducción a algoritmos del MIT] parece contradecir la condición 3. La página 4 muestra un árbol RB donde la altura de la rama izquierda es 2 y la rama derecha es 4. ¿Puede ofrecerme alguna aclaración? Quizás no entiendo la definición de un subárbol. [1]: ocw.mit.edu/courses/electrical-engineering-and-computer-science/…
i8abug
La diferencia parece provenir de esta definición en las notas del curso. Todas las rutas simples desde cualquier nodo x hasta una hoja descendiente tienen el mismo número de nodos negros = altura negra (x)
i8abug
Solo para continuar, encontré una definición que cambia el punto (3) en su respuesta a "cada hoja está 'no más que una cierta distancia' de la raíz que cualquier otra hoja". Esto parece satisfacer ambos casos. Aquí está el enlace de algunos cursos aleatorios
i8abug
8

Si el árbol binario está equilibrado o no, se puede verificar mediante el cruce de orden de nivel:

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;
}
suerte
fuente
1
Excelente respuesta. Creo que cumple con todos los requisitos que Eric publicó con respecto a Bonus y Super-Bonus. Es iterativo (usando una cola) y no recursivo, por lo que la pila de llamadas no se desbordará y trasladaremos todos los problemas de memoria al montón. Ni siquiera requiere atravesar todo el árbol. Se mueve nivel por nivel, por lo que si un árbol está muy desequilibrado en un lado, lo encontrará muy pronto (¿lo más pronto posible? Mucho antes que la mayoría de los algoritmos recursivos, aunque podría implementar un algoritmo iterativo transversal posterior al pedido que encontrará el último nivel desequilibra antes pero actuará peor en los primeros niveles). Entonces +1 :-)
David Refaeli
7

Esto se está volviendo mucho más complicado de lo que realmente es.

El algoritmo es como sigue:

  1. Sea A = profundidad del nodo de nivel más alto
  2. Sea B = profundidad del nodo de nivel más bajo

  3. Si abs (AB) <= 1, entonces el árbol está equilibrado

Miguel
fuente
¡Simple y directo!
Wasim Thabraze
3
Dos problemas, no es tan eficiente como podría ser, estás haciendo dos pasadas por todo el árbol. Y para los árboles que tienen un nodo a la izquierda y miles a la derecha, recorre innecesariamente todo, cuando podría haberse detenido después de 3 controles.
Eric Leschinski
5

Lo que significa equilibrado depende un poco de la estructura en cuestión. Por ejemplo, un árbol B no puede tener nodos a más de una cierta profundidad desde la raíz, o menos, todos los datos viven a una profundidad fija desde la raíz, pero puede estar desequilibrado si la distribución de hojas a hojas -pero uno de los nodos es desigual. Listas de omisión No tienen ninguna noción de equilibrio, confiando en cambio en la probabilidad para lograr un desempeño decente. Los árboles de Fibonacci se desequilibran a propósito, posponiendo el reequilibrio para lograr un rendimiento asintótico superior a cambio de actualizaciones ocasionalmente más largas. Los árboles AVL y Red-Black adjuntan metadatos a cada nodo para lograr un invariante de equilibrio de profundidad.

Todas estas estructuras y más están presentes en las bibliotecas estándar de los sistemas de programación más comunes (¡excepto python, RAGE!). Implementar uno o dos es una buena práctica de programación, pero probablemente no sea un buen uso del tiempo para lanzar el suyo propio para la producción, a menos que su problema tenga un rendimiento peculiar que no necesite ser satisfecho por ninguna colección estándar.

SingleNegationElimination
fuente
4

Nota 1: La altura de cualquier subárbol se calcula solo una vez.

Nota 2: Si el subárbol izquierdo no está equilibrado, se omite el cálculo del subárbol derecho, que potencialmente contiene millones de elementos.

// 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;
}
Arun
fuente
3

El equilibrio generalmente depende de la longitud del camino más largo en cada dirección. El algoritmo anterior no lo hará por usted.

¿Qué estás intentando implementar? Hay árboles que se equilibran a sí mismos alrededor (AVL / Rojo-negro). De hecho, los árboles de Java están equilibrados.

Uri
fuente
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
fuente
Creo que esta solución no es correcta. Si pasa un árbol que tiene un solo nodo, es decir, una raíz, devolverá como maxDepth 1(lo mismo para minDepth). Sin embargo, la profundidad correcta debería ser 0.La raíz de un árbol siempre tiene 0profundidad
Cratylus
3

Aquí hay una solución completa probada resuelta en C # (lo siento, no soy un desarrollador de Java) (solo copie y pegue en la aplicación de consola). Sé que la definición de equilibrado varía, por lo que no a todos les pueden gustar los resultados de mi prueba, pero solo mire el enfoque ligeramente diferente de verificar la profundidad / altura en un bucle recursivo y salir en la primera discrepancia sin guardar la altura / nivel / profundidad del nodo en cada nodo (solo manteniéndolo en una llamada de función).

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
fuente
No entiendo cómo alguien podría votar en negativo esta respuesta dentro de los 2 minutos posteriores a la publicación de la respuesta. El voto negativo está bien, pero ¿podría explicar qué hay de malo en esta solución?
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
fuente
es posible que desee agregar algunos comentarios
jgauffin
2

RE: La solución de @ lucky usa un BFS para hacer un recorrido de orden de nivel.

Atravesamos el árbol y mantenemos una referencia a vars min / max-level que describen el nivel mínimo en el que un nodo es una hoja.

Creo que la solución @lucky requiere una modificación. Como lo sugiere @codaddict, en lugar de verificar si un nodo es una hoja, debemos verificar si el hijo izquierdo o derecho es nulo (no ambos). De lo contrario, el algoritmo consideraría esto como un árbol equilibrado válido:

     1
    / \
   2   4
    \   \
     3   1

En 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 solución debe satisfacer todas las estipulaciones provistas en la pregunta inicial, operando en O (n) tiempo y O (n) espacio. El desbordamiento de memoria se dirigiría al montón en lugar de soplar una pila de llamadas recursiva.

Alternativamente, podríamos atravesar inicialmente el árbol para calcular + las alturas máximas de caché para cada subárbol raíz de forma iterativa. Luego, en otra ejecución iterativa, verifique si las alturas en caché de los subárboles izquierdo y derecho para cada raíz nunca difieren en más de uno. Esto también se ejecutaría en el tiempo O (n) y el espacio O (n), pero de forma iterativa para no causar un desbordamiento de la pila.

vikasnair
fuente
1

Bueno, necesita una forma de determinar las alturas de la izquierda y la derecha, y si la izquierda y la derecha están equilibradas.

Y yo solo return height(node->left) == height(node->right);

En cuanto a escribir una heightfunción, lea: Comprendiendo la recursividad

tpdi
fuente
3
Desea que las alturas izquierda y derecha estén dentro de 1, no necesariamente iguales.
Alex B
1

¿De qué tipo de árbol estás hablando? Hay árboles que se equilibran por sí mismos . Verifique sus algoritmos donde determinan si necesitan reordenar el árbol para mantener el equilibrio.

Lothar
fuente
1

Aquí hay una versión basada en un recorrido genérico de profundidad primero. Debe ser más rápido que la otra respuesta correcta y manejar todos los "desafíos" mencionados. Disculpas por el estilo, realmente no conozco Java.

Aún puede hacerlo mucho más rápido si regresa temprano si el máximo y el mínimo están configurados y tienen una diferencia> 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
fuente
1
Un buen intento, pero claramente no funciona. Sea x un nodo nulo. Deje que un nodo de árbol no nulo se denote como (VALOR IZQUIERDO DERECHA). Considere el árbol (x A (x B x)). "raíz" apunta a los nodos A, B, A, B, A, B ... para siempre. ¿Quieres intentarlo de nuevo? Una pista: en realidad es más fácil sin los consejos de los padres.
Eric Lippert
@Eric: Ups, arreglado (creo). Bueno, estoy tratando de hacer esto sin memoria O (profundidad), y si la estructura no tiene punteros principales (a menudo los tiene), necesita usar una pila.
Potatoswatter
Entonces, lo que me está diciendo es que prefiere usar la memoria permanente O (n) en los punteros principales para evitar asignar memoria temporal O (d), donde log n <= d <= n? Esto parece una economía falsa.
Eric Lippert
Desafortunadamente, aunque ha solucionado el problema con el cruce, aquí hay un problema mucho mayor. Esto no prueba si un árbol está equilibrado, prueba si un árbol tiene todas sus hojas cerca del mismo nivel. Esa no es la definición de "equilibrado" que di. Considere el árbol ((((x D x) C x) B x) A x). Su código informa que esto está "equilibrado" cuando obviamente está desequilibrado al máximo. ¿Quieres intentarlo de nuevo?
Eric Lippert
@Eric respuesta 1: no es una economía falsa si ya usa los punteros de los padres para otra cosa. respuesta 2: claro, por qué no. Esta es una forma extraña de depurar ... No debería estar escribiendo a ciegas recorridos de nada a las 4 am ...
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
fuente
1
Debe agregar alguna descripción a su respuesta y / o comentarios a su muestra 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
fuente
0

Esto es lo que he probado para el ejercicio extra de Eric. Intento deshacerme de mis bucles recursivos y regresar tan pronto como encuentro que un subárbol no está equilibrado.

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
fuente
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;
    }
siempre
fuente
0

Un árbol vacío tiene una altura equilibrada. Un árbol binario T no vacío se equilibra si:

1) El subárbol izquierdo de T está equilibrado

2) El subárbol derecho de T está equilibrado

3) La diferencia entre las alturas del subárbol izquierdo y el subárbol derecho no es más de 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;
}

Complejidad del tiempo: O (n)

Saqlain
fuente
0

Para tener un mejor rendimiento, especialmente en árboles enormes, puede guardar la altura en cada nodo, por lo que es una compensación entre el espacio y el rendimiento:

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

Ejemplo de implementación de la adición y lo mismo para la eliminación

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
fuente
-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
fuente
-2

¿No funcionaría esto?

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

Cualquier árbol desequilibrado siempre fallaría en esto.

Sumit Kishore
fuente
4
Muchos árboles equilibrados también lo fallarán.
Brian