Comment déterminer si un arbre binaire est équilibré en Java

1. Vue d'ensemble

Les arbres sont l'une des structures de données les plus importantes en informatique. Nous sommes généralement intéressés par un arbre équilibré, en raison de ses propriétés précieuses . Leur structure permet d'effectuer des opérations comme des requêtes, des insertions, des suppressions en temps logarithmique.

Dans ce tutoriel, nous allons apprendre comment déterminer si un arbre binaire est équilibré.

2. Définitions

Tout d'abord, introduisons quelques définitions afin de nous assurer que nous sommes sur la même longueur d'onde:

  • Un arbre binaire - une sorte d'arbre où chaque nœud a zéro, un ou deux enfants
  • Une hauteur d'un arbre - une distance maximale d'une racine à une feuille (identique à la profondeur de la feuille la plus profonde)
  • Un arbre équilibré - une sorte d'arbre où, pour chaque sous-arbre, la distance maximale de la racine à n'importe quelle feuille est au plus plus grande de un que la distance minimale de la racine à n'importe quelle feuille

Nous pouvons trouver un exemple d'arbre binaire équilibré ci-dessous. Trois bords verts sont une simple visualisation de la façon de déterminer la hauteur, tandis que les chiffres indiquent le niveau.

3. Objets de domaine

Alors, commençons par une classe pour notre arbre:

public class Tree { private int value; private Tree left; private Tree right; public Tree(int value, Tree left, Tree right) { this.value = value; this.left = left; this.right = right; } } 

Par souci de simplicité, disons que chaque nœud a une valeur entière . Notez que si les arbres gauche et droit sont nuls, cela signifie que notre nœud est une feuille .

Avant de présenter notre méthode principale, voyons ce qu'elle doit renvoyer:

private class Result { private boolean isBalanced; private int height; private Result(boolean isBalanced, int height) { this.isBalanced = isBalanced; this.height = height; } }

Ainsi, pour chaque appel, nous aurons des informations sur la hauteur et l'équilibre.

4. Algorithme

Ayant une définition d'un arbre équilibré, nous pouvons proposer un algorithme. Ce que nous devons faire est de vérifier la propriété souhaitée pour chaque nœud . Cela peut être réalisé facilement avec une recherche récursive en profondeur d'abord.

Maintenant, notre méthode récursive sera appelée pour chaque nœud. De plus, il gardera une trace de la profondeur actuelle. Chaque appel renverra des informations sur la hauteur et l'équilibre.

Maintenant, jetons un œil à notre méthode de profondeur d'abord:

private Result isBalancedRecursive(Tree tree, int depth) { if (tree == null) { return new Result(true, -1); } Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1); Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1); boolean isBalanced = Math.abs(leftSubtreeResult.height - rightSubtreeResult.height) <= 1; boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1; return new Result(isBalanced && subtreesAreBalanced, height); }

Tout d'abord, nous devons considérer le cas si notre nœud est nul : nous retournerons true (ce qui signifie que l'arbre est équilibré) et -1 comme hauteur.

Ensuite, nous faisons deux appels récursifs pour le sous-arbre gauche et droit, en gardant la profondeur à jour .

À ce stade, nous avons effectué des calculs pour les enfants d'un nœud actuel. Maintenant, nous avons toutes les données nécessaires pour vérifier le solde:

  • la variable isBalanced vérifie la hauteur des enfants, et
  • substreesAreBalanced indique si les sous-arbres sont également équilibrés

Enfin, nous pouvons renvoyer des informations sur l'équilibre et la hauteur. Il peut également être judicieux de simplifier le premier appel récursif avec une méthode de façade:

public boolean isBalanced(Tree tree) { return isBalancedRecursive(tree, -1).isBalanced; }

5. Résumé

Dans cet article, nous avons expliqué comment déterminer si un arbre binaire est équilibré. Nous avons expliqué une approche de recherche en profondeur d'abord.

Comme d'habitude, le code source avec les tests est disponible over sur GitHub.