Balanced Binary Tree

+10

Le tableau root contient un arbre binaire. La racine se trouve à l’indice 0, les enfants de l’indice i se trouvent aux indices 2*i+1 (à gauche) et 2*i+2 (à droite), -1 indique un emplacement vide, et des entrées -1 supplémentaires peuvent se trouver à la fin.

Retournez true si l’arbre est équilibré en hauteur, c’est-à-dire si, à chaque nœud, les hauteurs des sous-arbres gauche et droit diffèrent d’au plus 1, et false sinon. La hauteur d’un sous-arbre est le nombre de nœuds sur son plus long chemin descendant ; un sous-arbre vide a une hauteur de 0.

Fonction

isBalanced(root: integer-array) → boolean

rootinteger-array: l’arbre binaire dans l’ordre par niveau, avec -1 pour une position vide
Renvoieboolean: vrai si les hauteurs des deux sous-arbres de chaque nœud diffèrent d’au plus 1, faux sinon

Contraintes

1 ≤ root.length ≤ 32767
Chaque root[i] vaut -1 ou une valeur telle que 0 ≤ root[i] ≤ 10⁵.
root[0] n'est jamais -1, donc l'arbre comporte au moins un nœud.
Le tableau peut se terminer par des entrées -1 supplémentaires après le dernier nœud.
Les deux enfants d’un emplacement vide sont également vides, et la profondeur est d’au plus 14.
Les valeurs des nœuds sont distinctes.

Exemples

Entrée: root = [5, 2, 9, -1, -1, 7, 11]
Sortie: true
Explication: Le sous-arbre gauche de la racine est constitué du seul nœud 2, de hauteur 1. Son sous-arbre droit, composé de 9, 7 et 11, a une hauteur de 2. Ils diffèrent de 1, et tous les autres nœuds ont deux sous-arbres de même hauteur.

Entrée: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Sortie: false
Explication: Les deux côtés de la racine ont une hauteur de 3, mais le nœud 3 ne respecte pas la condition : son sous-arbre gauche 1, 0 a une hauteur de 2 et son sous-arbre droit est vide.

Entrée: root = [4, 2, -1, 1]
Sortie: false
Explication: La racine a la chaîne 2, 1 à sa gauche, une hauteur de 2, et rien à sa droite, une hauteur de 0. Une différence de 2 est trop importante.

Pour aller plus loin

Peux-tu vérifier l’arbre sans récursion, en utilisant une pile explicite ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La règle s’applique à chaque nœud : un arbre dont la racine semble équilibrée peut donc tout de même échouer plus bas, comme c’est le cas du deuxième exemple au nœud 3. Un parcours en post-ordre calcule une seule fois la hauteur de chaque sous-arbre et propage un échec dès qu’il survient, en O(n).

Recalculez les hauteurs à chaque nœud

Intuition

Transforme la définition en code. height(i) vaut 0 à un emplacement vide et vaut 1 de plus que la hauteur du plus grand des deux enfants ailleurs. Compare les hauteurs des deux enfants à chaque nœud réel ; le premier nœud où elles diffèrent de plus de 1 donne la réponse false.

Chaque vérification parcourt tout le sous-arbre situé sous son nœud ; un nœud est donc parcouru une fois pour chaque nœud au-dessus de lui : O(n·h). Avec au plus 14 niveaux, un arbre complet de 16,383 nœuds demande environ 2 × 10^5 étapes. Une chaîne de n nœuds demanderait O(n²).

Algorithme

Définissez height(i) comme 0 pour un indice au-delà de la fin ou un -1, et comme 1 + max(height(2*i+1), height(2*i+2)) pour un nœud réel.
Parcourez chaque indice i qui contient un nœud réel.
Si height(2*i+1) et height(2*i+2) diffèrent de plus de 1, retournez false.
Si la boucle se termine sans échec, retournez true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Un seul parcours en post-ordre qui signale la hauteur ou un échec

Intuition

La vérification d’un nœud nécessite les hauteurs de ses deux sous-arbres, qui sont aussi les valeurs dont le nœud a besoin pour indiquer sa propre hauteur. Récupère donc les deux lors d’un seul parcours en post-ordre : chaque appel renvoie la hauteur de son sous-arbre après le retour des deux enfants.

Un échec plus bas doit également remonter. Une hauteur réelle n’est jamais négative, donc utilise -1 pour le signaler : un appel renvoie -1 lorsqu’un enfant a renvoyé -1 ou lorsque les hauteurs des enfants diffèrent de plus de 1. Dans le deuxième exemple, le 3 voit les hauteurs 2 et 0 et renvoie -1, et la racine transmet cette valeur sans parcourir son côté droit.

Aucun nœud n’est visité deux fois, donc le temps d’exécution est O(n), avec O(h) appels sur la pile.

Algorithme

Écris check(i). Pour un indice au-delà de la fin ou un -1, renvoie 0.
Calcule left = check(2*i+1). Si sa valeur est -1, renvoie -1.
Calcule right = check(2*i+2). Si sa valeur est -1, ou si left et right diffèrent de plus de 1, renvoie -1.
Sinon, renvoie 1 + max(left, right).
Renvoie si check(0) est différent de -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Pièges et cas limites

Vérifier uniquement la racine. Dans le deuxième exemple, les deux côtés de la racine ont une hauteur de 3, et pourtant le nœud 3 a un écart de 2.
Comparer la feuille la moins profonde et la plus profonde. Le plus petit arbre équilibré de hauteur 6 a des feuilles aux profondeurs 4 et 6, et tous ses nœuds sont équilibrés.
Perdre une défaillance lors de la remontée. Si un enfant renvoie -1 et que le parent calcule 1 + max(-1, 2), la défaillance redevient une hauteur.
Utiliser la longueur du tableau comme hauteur. Les entrées -1 à la fin rendent le tableau plus long que la profondeur de l’arbre.
En Lua et en R, les tableaux commencent à l’indice 1. Garder les indices des nœuds à partir de 0 pour 2*i+1 et lire root[i + 1].

Questions fréquentes3

Quelle est la complexité temporelle d’un arbre binaire équilibré ?

Un parcours en postordre visite chaque nœud une seule fois : un temps de O(n) et un espace de pile de O(h) pour un arbre de hauteur h. Recalculer les hauteurs à chaque nœud coûte O(n·h), ce qui devient O(n²) sur une chaîne.

Que signifie « équilibré en hauteur » pour un arbre binaire ?

À chaque nœud, les hauteurs des sous-arbres gauche et droit diffèrent d’au plus 1. Les arbres AVL rétablissent cette propriété après chaque insertion et suppression, ce qui maintient leur hauteur à O(log n).

Un arbre binaire complet est-il toujours équilibré ?

Oui. Tous les niveaux d’un arbre complet sont pleins, à l’exception éventuelle du dernier, qui se remplit de gauche à droite ; ainsi, à chaque nœud, les hauteurs des deux sous-arbres diffèrent d’au plus 1. La réciproque est fausse : un arbre équilibré peut présenter des lacunes à gauche de son dernier niveau.

def isBalanced(root):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, -1, -1, 7, 11]

Résultat attendu

true