Validate Binary Search Tree

Q: Pourquoi vérifier chaque nœud par rapport à ses enfants ne suffit-il pas pour valider un BST ?

La règle s’applique à des sous-arbres entiers. Un nœud situé profondément dans le sous-arbre droit de la racine doit être supérieur à la racine, même s’il est le fils gauche d’un nœud beaucoup plus grand. Dans [10, 5, 15, -1, -1, 6, 20] , le 6 est un fils gauche correct de 15 , mais il se trouve à droite de 10 ; l’arbre n’est donc pas un arbre de recherche. Tu dois tenir compte des limites imposées par tous les ancêtres, pas seulement par le parent.

Q: Quelle est la complexité temporelle de la validation d’un arbre binaire de recherche ?

Les deux méthodes classiques, la vérification par parcours infixe et la vérification des intervalles, examinent chaque nœud une seule fois et prennent donc un temps de O(n) . La vérification des intervalles nécessite un espace supplémentaire de O(h) pour la pile, où h est la profondeur. Comparer chaque nœud à ses sous-arbres entiers fonctionne aussi, mais coûte O(n × h) , ce qui atteint O(n²) sur un arbre en forme de chemin.

Q: Peux-tu valider un BST avec un parcours infixe sans stocker chaque valeur ?

Oui. La vérification dans l’ordre compare toujours une valeur avec celle qui la précède immédiatement ; conserve donc la valeur précédente dans une variable plutôt que dans une liste. Parcours l’arbre dans l’ordre, par récursion ou à l’aide d’une pile explicite, et renvoie false dès qu’une valeur n’est pas supérieure à la précédente. Cela réduit l’espace supplémentaire à O(h) .

Q: Un arbre binaire de recherche peut-il contenir des valeurs en double ?

Pas selon la définition stricte utilisée ici : chaque valeur à gauche doit être plus petite et chaque valeur à droite plus grande, donc deux valeurs égales ne peuvent jamais convenir toutes les deux. Certains manuels autorisent les doublons d’un côté, par exemple les valeurs égales à droite. Selon cette règle, tu remplacerais une des comparaisons strictes par ≤ ; lis donc la définition avant d’écrire la vérification.

MoyenArbre binaire de recherche Parcours d’arbre

+10

On vous donne un arbre binaire stocké dans le tableau tree en ordre par niveaux. La racine se trouve à l’indice 0, les enfants du nœud à l’indice i se trouvent aux indices 2*i+1 (gauche) et 2*i+2 (droite), -1 indique un emplacement vide, et le tableau peut se terminer par des entrées -1 supplémentaires.

Écrivez une fonction nommée isValidBST qui renvoie true si l’arbre est un arbre binaire de recherche et false dans le cas contraire. Dans un arbre binaire de recherche, la valeur de chaque nœud est strictement supérieure à toutes les valeurs de son sous-arbre gauche et strictement inférieure à toutes celles de son sous-arbre droit. Deux valeurs égales ne peuvent jamais se trouver toutes les deux dans un arbre valide.

Fonction

isValidBST(tree: integer-array) → boolean

treeinteger-array: l’arbre binaire par ordre de niveau, avec -1 pour un emplacement vide
Renvoieboolean: vrai si l’arbre est un arbre binaire de recherche, faux sinon

Contraintes

1 ≤ tree.length ≤ 32767
Chaque tree[i] vaut -1 ou une valeur telle que 0 ≤ tree[i] ≤ 10⁵.
tree[0] n'est jamais -1, donc l'arbre contient 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 peuvent se répéter.

Exemples

Entrée: tree = [8, 3, 12, 1, 6, 10, 15]
Sortie: true
Explication: Chaque nœud se trouve du bon côté de tous les nœuds situés au-dessus de lui. En lisant dans l’ordre (sous-arbre gauche, nœud, sous-arbre droit), on obtient les valeurs 1, 3, 6, 8, 10, 12, 15, strictement croissantes, ce qui est caractéristique d’un arbre de recherche.

Entrée: tree = [10, 5, 15, -1, -1, 6, 20]
Sortie: false
Explication: Chaque nœud est plus grand que son enfant gauche et plus petit que son enfant droit, pourtant l’arbre n’est pas valide. Le 6 à l’index 5 se trouve dans le sous-arbre droit de la racine 10 ; il doit donc être supérieur à 10, ce qui n’est pas le cas.

Entrée: tree = [12, 7, 12]
Sortie: false
Explication: Le fils droit de la racine contient 12, la même valeur que la racine. Le sous-arbre droit doit être strictement supérieur, donc une valeur égale enfreint la règle.

+16 tests cachés à la soumission

Pour aller plus loin

Le parent du nœud à l’indice i se trouve à (i-1)/2, arrondi à l’entier inférieur. Peux-tu parcourir l’arbre dans l’ordre avec un espace supplémentaire de O(1), en passant par les parents plutôt qu’en utilisant une pile ou la récursion ?

Indices

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

0 sur 3 ouverts

Solution

La règle concerne les sous-arbres entiers, et non un nœud et ses deux enfants. Un arbre peut réussir le test du parent et des enfants à chaque nœud tout en étant incorrect, car un nœud situé profondément dans l’arbre peut enfreindre une limite fixée par un ancêtre situé plusieurs niveaux plus haut. Deux idées permettent de gérer cela proprement : parcourir l’arbre dans l’ordre et vérifier que les valeurs augmentent strictement, ou transmettre à chaque nœud l’intervalle de valeurs autorisées par ses ancêtres et vérifier que sa valeur appartient à cet intervalle.

Comparez chaque nœud à ses sous-arbres complets

Intuition

D’abord, voyons comment parcourir le tableau. Le nœud à l’indice i a son fils gauche à l’indice 2*i+1 et son fils droit à l’indice 2*i+2. Un fils est réel uniquement si son indice se trouve dans le tableau et si la valeur correspondante n’est pas -1. Dans [10, 5, 15, -1, -1, 6, 20], la racine 10 a 5 et 15 aux indices 1 et 2, et le nœud 15 a 6 et 20 aux indices 5 et 6.

La première idée que la plupart des gens essaient consiste à comparer chaque nœud uniquement à ses deux fils. Cet arbre explique pourquoi cela échoue : 5 < 10, 15 > 10, 6 < 15 et 20 > 15 sont toutes des relations vraies, mais le nœud 6 se trouve à droite de 10. La définition porte sur toutes les valeurs d’un sous-arbre ; vérifiez donc précisément cela.

Pour un nœud contenant v, toutes les valeurs de son sous-arbre gauche sont inférieures à v exactement lorsque la plus grande valeur à gauche est inférieure à v. De même, toutes les valeurs de son sous-arbre droit sont supérieures à v lorsque la plus petite valeur à cet endroit est supérieure à v. Deux petites fonctions auxiliaires récursives trouvent respectivement la plus grande et la plus petite valeur. Pour un côté vide, la plus grande valeur est -1 et la plus petite est 100001, des valeurs situées hors de l’intervalle autorisé ; un côté vide ne peut donc jamais faire échouer la vérification.

Cette méthode est correcte, mais elle répète du travail. Un nœud est parcouru une fois pour chaque ancêtre situé au-dessus de lui, le total est donc d’environ n × h visites pour un arbre de profondeur h. Une profondeur maximale de 14 convient ici, mais pour un arbre qui forme un seul chemin de n nœuds, le coût augmente jusqu’à O(n²).

Algorithme

Parcours chaque indice i dont la valeur n’est pas -1.
Trouve la plus grande valeur dans le sous-arbre gauche qui commence à 2*i+1, ou -1 si cet emplacement est vide.
Trouve la plus petite valeur dans le sous-arbre droit qui commence à 2*i+2, ou 100001 si cet emplacement est vide.
Si la plus grande valeur est supérieure ou égale à tree[i], ou si la plus petite valeur est inférieure ou égale à tree[i], renvoie false.
Après le dernier nœud, renvoie true.

def isValidBST(tree):
    n = len(tree)

    def largest(i):
        # Largest value in the subtree at index i, or -1 when that spot is empty.
        if i >= n or tree[i] == -1:
            return -1
        return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))

    def smallest(i):
        # Smallest value in the subtree at index i, or 100001 when that spot is empty.
        if i >= n or tree[i] == -1:
            return 100001
        return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))

    for i in range(n):
        if tree[i] == -1:
            continue
        # Everything on the left must be smaller, everything on the right larger.
        if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
            return False
    return True

Les valeurs en parcours infixe doivent augmenter strictement

Intuition

Un parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit. Dans un arbre binaire de recherche, cet ordre est trié : tout ce qui se trouve à gauche est plus petit, donc vient en premier, et tout ce qui se trouve à droite est plus grand, donc vient après. Le premier exemple donne 1, 3, 6, 8, 10, 12, 15.

L’implication inverse est également vraie, et c’est ce qui en fait un test. Prenez n’importe quel nœud v. Dans la séquence infixe, tout son sous-arbre gauche se trouve juste avant lui et tout son sous-arbre droit juste après. Si la séquence est strictement croissante, chaque valeur précédant v est plus petite et chaque valeur le suivant est plus grande : la règle est donc respectée pour v, et de la même manière pour tous les autres nœuds.

Parcourez donc l’arbre dans l’ordre infixe, recueillez les valeurs et comparez chacune à celle qui la précède. Le deuxième exemple donne 5, 10, 6, 15, 20 : le passage de 10 à 6 révèle le nœud placé du mauvais côté. Le troisième donne 7, 12, 12, et la répétition de 12 échoue au test strict. Chaque nœud est visité une fois : le temps d’exécution est de O(n), et la liste occupe O(n) espace.

Algorithme

Écris walk(i) : si l’emplacement est vide, arrête-toi ; sinon, parcours 2*i+1, ajoute tree[i], puis parcours 2*i+2.
Appelle walk(0) pour recueillir les valeurs dans l’ordre.
Pour chaque position k à partir de 1, si values[k-1] ≥ values[k], renvoie false.
Renvoie true.

def isValidBST(tree):
    n = len(tree)
    values = []

    def walk(i):
        # Left subtree, then the node, then the right subtree.
        if i >= n or tree[i] == -1:
            return
        walk(2 * i + 1)
        values.append(tree[i])
        walk(2 * i + 2)

    walk(0)
    # A search tree read in order gives strictly increasing values.
    for k in range(1, len(values)):
        if values[k - 1] >= values[k]:
            return False
    return True

Transmettez la plage autorisée le long de l’arbre

Intuition

Considère la règle du point de vue d’un nœud. Chaque ancêtre lui impose une limite. Si le nœud se trouve dans le sous-arbre gauche d’un ancêtre contenant a, sa valeur doit être inférieure à a ; s’il se trouve dans le sous-arbre droit, elle doit être supérieure à a. Toutes ces limites réunies forment un intervalle ouvert (low, high), et le nœud est exactement à la bonne place lorsque sa valeur se trouve strictement à l’intérieur de cet intervalle.

Tu peux construire cet intervalle en descendant. La racine n’a aucune limite. En passant d’un nœud contenant v à son enfant gauche, on conserve low et on abaisse high à v ; en passant à son enfant droit, on conserve high et on élève low à v. La nouvelle limite est toujours plus stricte que celle qu’elle remplace, car v a lui-même passé la vérification dans l’ancien intervalle.

Dans le deuxième exemple, 15 reçoit l’intervalle (10, no limit) et le transmet à son enfant gauche sous la forme (10, 15). Le 6 est inférieur à 10, donc la vérification échoue immédiatement, sans examiner aucun autre nœud. Les valeurs sont comprises entre 0 et 10^5, donc -1 et 100001 servent de « sans limite ».

Garde les nœuds en attente sur une pile, chacun avec son intervalle. Chaque nœud est vérifié une fois, en temps O(n), et la pile contient les nœuds en attente le long d’un seul chemin, soit un espace de O(h). Le premier intervalle invalide met fin à la recherche.

Algorithme

Empilez (0, -1, 100001) : l'indice de la racine et un intervalle ouvert sans limite réelle.
Dépilez (i, low, high). Si tree[i] n'est pas strictement compris entre low et high, renvoyez false.
Si l'enfant gauche 2*i+1 existe, empilez-le avec l'intervalle (low, tree[i]).
Si l'enfant droit 2*i+2 existe, empilez-le avec l'intervalle (tree[i], high).
Lorsque la pile est vide, renvoyez true.

def isValidBST(tree):
    n = len(tree)
    # Each entry: a node index and the open range (low, high) its value must fall in.
    # -1 and 100001 lie outside every allowed value, so they mean "no limit".
    stack = [(0, -1, 100001)]
    while stack:
        i, low, high = stack.pop()
        value = tree[i]
        if not (low < value < high):
            return False
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append((left, low, value))  # the left side must stay below value
        if right < n and tree[right] != -1:
            stack.append((right, value, high))  # the right side must stay above value
    return True

Pièges et cas limites

La plupart des réponses erronées ne vérifient pas assez de choses, ou vérifient la bonne chose avec la mauvaise comparaison.

Comparer un nœud uniquement avec ses enfants. Dans [10, 5, 15, -1, -1, 6, 20], chaque paire parent-enfant semble correcte, mais le 6 enfreint toujours la limite fixée par la racine deux niveaux plus haut.
Autoriser les valeurs égales. L’ordre est strict des deux côtés, donc [12, 7, 12] n’est pas valide. Utilisez low < v < high et values[k-1] < values[k], jamais ≤.
Transmettre uniquement la valeur du parent. Un enfant gauche a besoin des deux limites : être inférieur à son parent et supérieur à la limite inférieure que le parent avait. Transmettez l’intervalle complet.
Choisir une valeur « sans limite » qu’un nœud peut contenir. Les valeurs commencent à 0, donc une limite inférieure de 0 rejetterait un nœud valide contenant 0, comme dans [0]. Commencez en dessous de toutes les valeurs autorisées.
Lire au-delà de la fin du tableau. Vérifiez 2*i+1 < tree.length avant de lire un enfant, et considérez -1 comme l’absence d’enfant.
Confondre le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les indices des nœuds basés sur 0 pour le calcul 2*i+1 et lisez tree[i + 1].

Questions fréquentes4

Pourquoi vérifier chaque nœud par rapport à ses enfants ne suffit-il pas pour valider un BST ?

La règle s’applique à des sous-arbres entiers. Un nœud situé profondément dans le sous-arbre droit de la racine doit être supérieur à la racine, même s’il est le fils gauche d’un nœud beaucoup plus grand. Dans [10, 5, 15, -1, -1, 6, 20], le 6 est un fils gauche correct de 15, mais il se trouve à droite de 10 ; l’arbre n’est donc pas un arbre de recherche. Tu dois tenir compte des limites imposées par tous les ancêtres, pas seulement par le parent.

Quelle est la complexité temporelle de la validation d’un arbre binaire de recherche ?

Les deux méthodes classiques, la vérification par parcours infixe et la vérification des intervalles, examinent chaque nœud une seule fois et prennent donc un temps de O(n). La vérification des intervalles nécessite un espace supplémentaire de O(h) pour la pile, où h est la profondeur. Comparer chaque nœud à ses sous-arbres entiers fonctionne aussi, mais coûte O(n × h), ce qui atteint O(n²) sur un arbre en forme de chemin.

Peux-tu valider un BST avec un parcours infixe sans stocker chaque valeur ?

Oui. La vérification dans l’ordre compare toujours une valeur avec celle qui la précède immédiatement ; conserve donc la valeur précédente dans une variable plutôt que dans une liste. Parcours l’arbre dans l’ordre, par récursion ou à l’aide d’une pile explicite, et renvoie false dès qu’une valeur n’est pas supérieure à la précédente. Cela réduit l’espace supplémentaire à O(h).

Un arbre binaire de recherche peut-il contenir des valeurs en double ?

Pas selon la définition stricte utilisée ici : chaque valeur à gauche doit être plus petite et chaque valeur à droite plus grande, donc deux valeurs égales ne peuvent jamais convenir toutes les deux. Certains manuels autorisent les doublons d’un côté, par exemple les valeurs égales à droite. Selon cette règle, tu remplacerais une des comparaisons strictes par ≤ ; lis donc la définition avant d’écrire la vérification.

Python

def isValidBST(tree):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

tree = [8, 3, 12, 1, 6, 10, 15]

Attendu

true

Validate Binary Search Tree

Fonction

Contraintes

Exemples

Indices

Solution

Comparez chaque nœud à ses sous-arbres complets

Les valeurs en parcours infixe doivent augmenter strictement

Transmettez la plage autorisée le long de l’arbre

Pièges et cas limites

Questions fréquentes4

Problèmes similaires