Comment déterminer si l'arbre binaire est équilibré?

Cela fait un moment depuis ces années d'école. J'ai trouvé un emploi de spécialiste informatique dans un hôpital. Essayer de bouger pour faire de la programmation réelle maintenant. Je travaille maintenant sur des arbres binaires, et je me demandais quel serait le meilleur moyen de déterminer si l'arbre est équilibré en hauteur.

Je pensais à quelque chose le long de ceci:

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

Est-ce une bonne implémentation? ou est-ce que je manque quelque chose?

Je suis tombé sur cette vieille question en cherchant autre chose. Je remarque que vous n’avez jamais obtenu de réponse complète.

La manière de résoudre ce problème est de commencer par écrire une spécification pour la fonction que vous essayez d'écrire.

Spécification: Un arbre binaire bien formé est dit "équilibré en hauteur" si (1) il est vide, ou (2) ses enfants gauche et droit sont équilibrés en hauteur et la hauteur de l'arbre gauche est à moins de 1 hauteur de l'arbre droit.

Maintenant que vous avez la spécification, le code est simple à écrire. Suivez simplement les spécifications:

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

Traduire cela dans le langage de programmation de votre choix devrait être trivial.

Exercice bonus : ce schéma de code naïf parcourt l'arbre beaucoup trop de fois lors du calcul des hauteurs. Pouvez-vous le rendre plus efficace?

Exercice super bonus : supposons que l'arbre soit massivement déséquilibré. Comme, un million de nœuds de profondeur d'un côté et trois de profondeur de l'autre. Existe-t-il un scénario dans lequel cet algorithme fait exploser la pile? Pouvez-vous corriger l'implémentation pour qu'elle ne fasse jamais exploser la pile, même si on lui donne un arbre massivement déséquilibré?

MISE À JOUR : Donal Fellows souligne dans sa réponse qu'il existe différentes définitions de «équilibré» que l'on pourrait choisir. Par exemple, on pourrait prendre une définition plus stricte de «hauteur équilibrée», et exiger que la longueur du chemin vers l' enfant vide le plus proche se trouve dans l'un des chemins vers l' enfant vide le plus éloigné . Ma définition est moins stricte que cela, et admet donc plus d'arbres.

On peut aussi être moins strict que ma définition; on pourrait dire qu'un arbre équilibré est celui dans lequel la longueur maximale du chemin vers un arbre vide sur chaque branche ne diffère pas de plus de deux, ou trois, ou d'une autre constante. Ou que la longueur maximale du chemin est une fraction de la longueur minimale du chemin, comme un demi ou un quart.

Cela n'a vraiment pas d'importance en général. Le but de tout algorithme d'équilibrage d'arbres est de s'assurer que vous ne vous retrouvez pas dans la situation où vous avez un million de nœuds d'un côté et trois de l'autre. La définition de Donal est bonne en théorie, mais en pratique, il est difficile de trouver un algorithme d'équilibrage d'arbres qui répond à ce niveau de rigueur. Les économies de performances ne justifient généralement pas le coût de mise en œuvre. Vous passez beaucoup de temps à faire des réarrangements inutiles des arbres afin d'atteindre un niveau d'équilibre qui en pratique fait peu de différence. Qui se soucie si parfois il faut quarante branches pour atteindre la feuille la plus éloignée dans un arbre imparfaitement équilibré à millions de nœuds alors qu'il ne pourrait en théorie en prendre que vingt dans un arbre parfaitement équilibré? Le fait est qu'il ne faut jamais un million. Passer du pire des cas d'un million à un pire des cas de quarante est généralement suffisant; vous n'êtes pas obligé d'aller jusqu'au cas optimal.

L'équilibre est une propriété vraiment subtile; vous pensez savoir ce que c'est, mais il est si facile de se tromper. En particulier, même la (bonne) réponse d'Eric Lippert est erronée. C'est parce que la notion de hauteur ne suffit pas. Vous devez avoir le concept des hauteurs minimales et maximales d'un arbre (où la hauteur minimale est le plus petit nombre de marches entre la racine et une feuille, et le maximum est ... eh bien, vous obtenez l'image). Compte tenu de cela, nous pouvons définir l'équilibre comme étant:

Un arbre dont la hauteur maximale d'une branche ne dépasse pas un de plus que la hauteur minimale d'une branche.

(Cela implique en fait que les branches sont elles-mêmes équilibrées; vous pouvez choisir la même branche pour le maximum et le minimum.)

Tout ce que vous devez faire pour vérifier cette propriété est une simple traversée d'arbre en gardant une trace de la profondeur actuelle. La première fois que vous revenez en arrière, cela vous donne une profondeur de référence. Chaque fois que vous revenez en arrière, vous comparez la nouvelle profondeur à la ligne de base

• si c'est égal à la ligne de base, alors vous continuez
• s'il y en a plus d'un différent, l'arbre n'est pas équilibré
• s'il s'agit d'un seul, vous connaissez maintenant la plage d'équilibre et toutes les profondeurs suivantes (lorsque vous êtes sur le point de revenir en arrière) doivent être la première ou la deuxième valeur.

Dans du code:

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

Je suppose que vous pouvez le faire sans utiliser le modèle Observer, mais je trouve plus facile de raisonner de cette façon.

[EDIT]: Pourquoi vous ne pouvez pas simplement prendre la hauteur de chaque côté. Considérez cet arbre:

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

OK, un désordre de peu, mais chaque côté de la racine est équilibrée: Cest la profondeur 2, A, B, D, Esont la profondeur 3, et F, G, H, Jsont la profondeur 4. La hauteur de la branche gauche est 2 (souvenez - vous de la hauteur diminue à mesure que vous traversez la branche), la hauteur de la branche droite est 3. Pourtant, l'arbre global n'est pas équilibré car il y a une différence de hauteur de 2 entre Cet F. Vous avez besoin d'une spécification minimax (bien que l'algorithme réel puisse être moins complexe car il ne devrait y avoir que deux hauteurs autorisées).

Cela détermine uniquement si le niveau supérieur de l'arborescence est équilibré. Autrement dit, vous pourriez avoir un arbre avec deux longues branches à l'extrême gauche et à l'extrême droite, sans rien au milieu, et cela reviendrait vrai. Vous devez vérifier de manière récursive les root.leftet root.rightpour voir s'ils sont également équilibrés en interne avant de renvoyer true.

Réponse d'exercice bonus. La solution simple. De toute évidence, dans une implémentation réelle, on pourrait envelopper ceci ou quelque chose pour éviter d'exiger que l'utilisateur inclue la hauteur dans sa réponse.

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     

Après la solution de commande, parcourez l'arbre une seule fois. La complexité temporelle est O (n), l'espace est O (1), c'est mieux que la solution descendante. Je vous donne une implémentation de version 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);
    }
}

La définition d'un arbre binaire à hauteur équilibrée est:

Arbre binaire dans lequel la hauteur des deux sous-arbres de chaque nœud ne diffère jamais de plus de 1.

Ainsi, un arbre binaire vide est toujours équilibré en hauteur.
Un arbre binaire non vide est équilibré en hauteur si:

1. Son sous-arbre gauche est équilibré en hauteur.
2. Son sous-arbre droit est équilibré en hauteur.
3. La différence entre les hauteurs du sous-arbre gauche et droit n'est pas supérieure à 1.

Considérez l'arbre:

    A
     \ 
      B
     / \
    C   D

Comme on le voit, le sous-arbre gauche de Aest équilibré en hauteur (car il est vide), tout comme son sous-arbre droit. Mais l'arbre n'est toujours pas équilibré en hauteur car la condition 3 n'est pas remplie car la hauteur du sous-arbre gauche l'est 0et la hauteur du sous-arbre droit l'est 2.

L'arbre suivant n'est pas non plus équilibré en hauteur même si la hauteur du sous-arbre gauche et droit est égale. Votre code existant retournera vrai pour cela.

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

Donc, le mot tout dans la def est très important.

Cela fonctionnera:

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

Lien Ideone

Si l'arbre binaire est équilibré ou non peut être vérifié par la traversée de l'ordre de niveau:

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

Cela devient beaucoup plus compliqué qu'il ne l'est en réalité.

L'algorithme est le suivant:

1. Soit A = profondeur du nœud de plus haut niveau

2. Soit B = profondeur du nœud le plus bas

3. Si abs (AB) <= 1, alors l'arbre est équilibré

Ce que signifie équilibré dépend un peu de la structure à portée de main. Par exemple, un arbre B ne peut pas avoir de nœuds à plus d'une certaine profondeur à partir de la racine, ou moins d'ailleurs, toutes les données vivent à une profondeur fixe à partir de la racine, mais il peut être déséquilibré si la distribution des feuilles aux feuilles -mais-un des nœuds est inégal. Skip-lists N'ont aucune notion d'équilibre, s'appuyant plutôt sur la probabilité d'atteindre des performances décentes. Les arbres de Fibonacci tombent délibérément en déséquilibre, reportant le rééquilibrage pour obtenir des performances asymptotiques supérieures en échange de mises à jour parfois plus longues. Les arbres AVL et Rouge-Noir attachent des métadonnées à chaque nœud pour atteindre un invariant d'équilibre de profondeur.

Toutes ces structures et bien d'autres sont présentes dans les bibliothèques standard de la plupart des systèmes de programmation courants (sauf python, RAGE!). Mettre en œuvre un ou deux est une bonne pratique de programmation, mais ce n'est probablement pas une bonne utilisation du temps pour lancer le vôtre pour la production, à moins que votre problème n'ait des performances particulières qui ne sont pas satisfaites par des collections standard.

Remarque 1: La hauteur de tout sous-arbre n'est calculée qu'une seule fois.

Remarque 2: Si le sous-arbre de gauche est déséquilibré, alors le calcul du sous-arbre de droite, contenant potentiellement un million d'éléments, est ignoré.

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

L'équilibrage dépend généralement de la longueur du chemin le plus long dans chaque direction. L'algorithme ci-dessus ne fera pas cela pour vous.

Qu'essayez-vous de mettre en œuvre? Il y a des arbres auto-équilibrés autour (AVL / Rouge-noir). En fait, les arbres Java sont équilibrés.

Si c'est pour votre travail , je suggère:

1. ne réinventez pas la roue et
2. utiliser / acheter des COTS au lieu de jouer avec des bits.
3. Économisez votre temps / énergie pour résoudre les problèmes commerciaux.

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

Voici une solution complète et testée en C # (désolé, je ne suis pas un développeur Java) (il suffit de copier-coller dans l'application console). Je sais que la définition d'équilibré varie, donc tout le monde ne peut pas aimer mes résultats de test, mais veuillez simplement regarder l'approche légèrement différente de la vérification de la profondeur / hauteur dans une boucle récursive et de la sortie au premier décalage sans enregistrer la hauteur / niveau / profondeur du nœud sur chaque nœud (le maintenir uniquement dans un appel de fonction).

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

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

RE: la solution de @ lucky utilisant un BFS pour effectuer un parcours par ordre de niveau.

Nous parcourons l'arbre et gardons une référence aux vars min / max-level qui décrivent le niveau minimum auquel un nœud est une feuille.

Je pense que la solution @lucky nécessite une modification. Comme suggéré par @codaddict, plutôt que de vérifier si un nœud est une feuille, nous devons vérifier si SOIT les enfants gauche ou droit sont nuls (pas les deux). Sinon, l'algorithme considérerait cela comme un arbre équilibré valide:

     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

Cette solution doit satisfaire toutes les stipulations fournies dans la question initiale, fonctionnant en temps O (n) et en espace O (n). Le débordement de mémoire serait dirigé vers le tas plutôt que de souffler une pile d'appels récursive.

Alternativement, nous pourrions initialement parcourir l'arborescence pour calculer les hauteurs max + cache pour chaque sous-arbre racine de manière itérative. Ensuite, dans une autre exécution itérative, vérifiez si les hauteurs mises en cache des sous-arbres gauche et droit pour chaque racine ne diffèrent jamais de plus d'un. Cela fonctionnerait également dans le temps O (n) et dans l'espace O (n) mais de manière itérative pour ne pas provoquer de débordement de pile.

Eh bien, vous avez besoin d'un moyen de déterminer les hauteurs de gauche et de droite, et si la gauche et la droite sont équilibrées.

Et je viens de return height(node->left) == height(node->right);

Quant à l'écriture d'une heightfonction, lisez: Comprendre la récursivité

De quel genre d'arbre parlez-vous? Il y a des arbres auto-équilibrés là-bas. Vérifiez leurs algorithmes où ils déterminent s'ils doivent réorganiser l'arbre afin de maintenir l'équilibre.

Voici une version basée sur un parcours générique en profondeur d'abord. Devrait être plus rapide que l'autre bonne réponse et gérer tous les «défis» mentionnés. Toutes mes excuses pour le style, je ne connais pas vraiment Java.

Vous pouvez toujours le rendre beaucoup plus rapide en revenant tôt si max et min sont tous les deux définis et ont une différence> 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 );
}

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

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

Voici ce que j'ai essayé pour l'exercice bonus d'Eric. J'essaye de dérouler mes boucles récursives et de revenir dès que je trouve qu'un sous-arbre n'est pas équilibré.

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
}

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

Un arbre vide est équilibré en hauteur. Un arbre binaire T non vide est équilibré si:

1) Le sous-arbre gauche de T est équilibré

2) Le sous-arbre droit de T est équilibré

3) La différence entre les hauteurs du sous-arbre gauche et du sous-arbre droit n'est pas supérieure à 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;
}

Complexité temporelle: O (n)

Pour avoir de meilleures performances, spécialement sur les arbres énormes, vous pouvez enregistrer la hauteur de chaque nœud, c'est donc un compromis entre l'espace et les performances:

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

Exemple de mise en œuvre de l'ajout et de même pour la suppression

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;

}

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

Cela ne fonctionnerait-il pas?

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

Tout arbre déséquilibré échouerait toujours.