Comment déterminer si un arbre binaire est équilibré ?

Question

Ça fait longtemps depuis ces années d'école. J'ai trouvé un emploi de spécialiste en informatique dans un hôpital. J'essaie de passer à la programmation proprement dite maintenant. Je travaille actuellement sur des arbres binaires et je me demandais quelle serait la meilleure façon de déterminer si l'arbre est équilibré en hauteur.

Je pensais à quelque chose comme ça :

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 mise en œuvre ? ou est-ce que je rate quelque chose ?

Answer 1

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 façon 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 de la hauteur de l'arbre droit.

Maintenant que vous avez la spécification, le code est trivial à écrire. Il suffit de suivre la spécification :

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 code naïf traverse l'arbre beaucoup trop de fois lors du calcul des hauteurs. Pouvez-vous le rendre plus efficace ?

Super exercice bonus : supposons que l'arbre soit massivement asymétrique. Par exemple, un million de noeuds d'un côté et trois de l'autre. Y a-t-il un scénario dans lequel cet algorithme fait sauter la pile ? Pouvez-vous corriger l'implémentation pour qu'il ne fasse jamais sauter la pile, même avec un arbre massivement déséquilibré ?

UPDATE : Donal Fellows souligne dans sa réponse qu'il existe différentes définitions du terme "é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 jusqu'à la le plus proche l'enfant vide se trouve dans l'un des chemins vers le le plus loin enfant vide. 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 un arbre 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 une autre constante. Ou que la longueur maximale du chemin est une fraction de la longueur minimale du chemin, comme la moitié ou le quart.

En général, cela n'a pas d'importance. Le but de tout algorithme d'équilibrage des 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 des arbres qui réponde à ce niveau de rigueur. Le gain de performance ne justifie généralement pas le coût de mise en œuvre. Vous passez beaucoup de temps à effectuer des réarrangements inutiles de l'arbre afin d'atteindre un niveau d'équilibre qui, en pratique, ne fait guère de différence. Qui se soucie du fait qu'il faille parfois quarante branches pour atteindre la feuille la plus éloignée dans un arbre imparfaitement équilibré d'un million de nœuds, alors qu'il n'en faudrait en théorie que vingt dans un arbre parfaitement équilibré ? Le fait est qu'il ne faut jamais un million. Passer du pire cas d'un million au pire cas de quarante est généralement suffisant ; il n'est pas nécessaire d'aller jusqu'au cas optimal.

Answer 2

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 fausse. C'est parce que la notion de hauteur n'est pas suffisant. Vous devez avoir le concept de hauteur minimale et maximale d'un arbre (où la hauteur minimale est le plus petit nombre de pas de la racine à une feuille, et le maximum est... eh bien, vous voyez le tableau). Cela étant, nous pouvons définir l'équilibre comme suit :

Un arbre dont la hauteur maximale de toute branche ne dépasse pas un plus que la hauteur minimale de toute 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 de l'arbre en gardant la trace de la profondeur actuelle. La première fois que vous revenez en arrière, cela vous donne une profondeur de base. Ensuite, à chaque fois que vous revenez en arrière, vous comparez la nouvelle profondeur à la profondeur de base.

• s'il est égal à la ligne de base, alors vous continuez simplement
• si c'est plus d'un différent, l'arbre n'est pas équilibré
• s'il s'agit d'une valeur unique, alors 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 soit la première, soit la deuxième valeur.

En 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 pourriez le faire sans utiliser le modèle Observer, mais je trouve que c'est 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 peu désordonné, mais chaque côté de la Racine est équilibré : C est la profondeur 2, A , B , D , E sont à la profondeur 3, et F , G , H , J sont de profondeur 4. La hauteur de la branche gauche est de 2 (rappelez-vous que la hauteur diminue à mesure que vous traversez la branche), la hauteur de la branche droite est de 3. Pourtant, l'arbre global est de no équilibré car il y a une différence de hauteur de 2 entre C y 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).

Answer 3

Cela détermine uniquement si le niveau supérieur de l'arbre est équilibré. En d'autres termes, vous pourriez avoir un arbre avec deux longues branches à l'extrême gauche et à l'extrême droite, sans rien au milieu, et cela renverrait vrai. Vous devez vérifier de manière récursive le root.left y root.right pour voir si elles sont également équilibrées en interne avant de renvoyer true.

Answer 4

Réponse à l'exercice bonus. La solution simple. Évidemment, dans une mise en œuvre réelle, on pourrait envelopper ceci ou quelque chose d'autre pour éviter de demander à l'utilisateur d'inclure la hauteur dans sa réponse.

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, out heightleft) and IsHeightBalanced(tree.right, out heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1

Answer 5

La définition d'un arbre binaire équilibré en hauteur est la suivante :

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

Donc, 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 de sous-arbres gauche et droit n'est pas supérieure à supérieure à 1.

Considérez l'arbre :

    A
     \ 
      B
     / \
    C   D

Comme on le voit, le sous-arbre gauche de A est équilibré en hauteur (puisqu'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 puisque la hauteur du sous-arbre gauche est 0 et la hauteur de la sous-arborescence droite est 2 .

L'arbre suivant n'est pas non plus équilibré en hauteur, même si les hauteurs des sous-arbres gauche et droit sont égales. Votre code existant retournera vrai pour cela.

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

Donc le mot chaque dans le def est très important.

Ça va marcher :

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 avec Ideone