Validate Binary Search Tree
Un arbre binaire est stocké dans le tableau tree selon l’ordre d’un tas : 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 une place vide, et le tableau peut se terminer par des entrées supplémentaires -1.
Écris isValidBST, qui renvoie true si l’arbre est un arbre binaire de recherche et false sinon. 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 les valeurs de son sous-arbre droit.
Fonction
- treeinteger-array
- l’arbre binaire par niveaux, avec -1 pour une position vide
- Renvoieboolean
- vrai si l’arbre est un arbre binaire de recherche, faux sinon
Contraintes
1 ≤ tree.length ≤ 32767- Chaque
tree[i]est-1ou une valeur telle que0 ≤ tree[i] ≤ 105. tree[0]n’est jamais-1, donc l’arbre a au moins un nœud.- Le tableau peut se terminer par des entrées
-1supplé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
- En lisant dans l’ordre (sous-arbre gauche, nœud, sous-arbre droit), les valeurs sont
1, 3, 6, 8, 10, 12, 15. Elles augmentent strictement, donc chaque nœud se trouve du bon côté de chacun de ses ancêtres.
- 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 le
6à l’index5se trouve dans le sous-arbre droit de la racine ; il doit donc être plus grand que10.
- Entrée
- tree = [12, 7, 12]
- Sortie
- false
- Explication
- Le fils droit de la racine contient
12, égal à la racine. Le sous-arbre droit doit être strictement supérieur, donc l’arbre n’est pas valide.
Pour aller plus loin
Le parent d’un nœud se trouve à l’indice (i-1)/2, arrondi à l’entier inférieur. Peux-tu parcourir l’arbre dans l’ordre avec O(1) espace supplémentaire, 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.
Dans
[10, 5, 15, -1, -1, 6, 20], chaque nœud est plus grand que son enfant gauche et plus petit que son enfant droit. Pourquoi n’est-ce toujours pas un arbre de recherche ?Chaque ancêtre impose une limite à un nœud : en dessous si le nœud se trouve à sa gauche, au-dessus s’il se trouve à sa droite. Ensemble, ces limites forment un intervalle ouvert. Aller à gauche depuis une valeur
vabaisse la limite supérieure àv; aller à droite élève la limite inférieure àv.Conservez une pile de
(index, low, high), en commençant par la racine et une plage plus large que toutes les valeurs autorisées. Dépilez une entrée, échouez si la valeur n’est pas strictement comprise dans la plage, puis empilez chaque enfant réel avec sa plage resserrée.
Solution
La règle s’applique à des sous-arbres entiers. Comparer chaque nœud à ses deux enfants ne suffit donc pas : un nœud situé profondément dans l’arbre peut enfreindre une limite fixée par un ancêtre plusieurs niveaux plus haut. Parcourez l’arbre dans l’ordre et vérifiez que les valeurs augmentent strictement, ou transmettez à chaque nœud l’intervalle autorisé par ses ancêtres.
Comparez chaque nœud à l’ensemble de ses sous-arbres
Intuition
Toutes les valeurs dans le sous-arbre gauche d’un nœud sont inférieures à sa valeur v exactement lorsque la plus grande valeur de ce sous-arbre est inférieure à v, et toutes les valeurs dans son sous-arbre droit sont supérieures à v exactement lorsque la plus petite valeur de ce sous-arbre est supérieure à v. Deux fonctions auxiliaires récursives permettent de les trouver. Un côté vide renvoie -1 ou 100001, des valeurs en dehors de l’intervalle des valeurs, de sorte que la condition n’échoue jamais.
Chaque nœud est parcouru une fois pour chacun de ses ancêtres, soit environ n × h visites pour un arbre de profondeur h. Avec une profondeur d’au plus 14, c’est peu coûteux, mais sur un chemin de n nœuds, le coût atteint O(n²).
Algorithme
- Parcours chaque indice
idont la valeur n’est pas-1. - Trouve la plus grande valeur dans le sous-arbre gauche à
2*i+1(-1s’il est vide) et la plus petite dans le sous-arbre droit à2*i+2(100001s’il est vide). - Si la plus grande valeur est supérieure ou égale à
tree[i], ou si la plus petite est inférieure ou égale àtree[i], retournefalse. - Retourne
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 TrueLes valeurs en parcours infixe doivent être strictement croissantes
Intuition
Un parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit ; dans un arbre binaire de recherche, il lit donc les valeurs dans l’ordre croissant.
L’inverse est également vrai. Pour tout nœud v, tout son sous-arbre gauche apparaît juste avant lui dans la séquence, 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 en v, comme en tout autre nœud.
Le deuxième exemple donne 5, 10, 6, 15, 20 : la baisse de 10 à 6 révèle le nœud mal placé. Chaque nœud est visité une seule fois : un temps de O(n) et un espace de O(n) pour la liste.
Algorithme
- Écris
walk(i): si l’emplacement est vide, arrête-toi ; sinon, parcours2*i+1, ajoutetree[i], puis parcours2*i+2. - Appelle
walk(0)pour recueillir les valeurs dans l’ordre. - Pour chaque position
kà partir de1, sivalues[k-1] ≥ values[k], renvoiefalse. - 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 TrueTransmettre la plage autorisée vers le bas de l’arbre
Intuition
Chaque ancêtre impose une limite à un nœud : inférieur à a si le nœud se trouve dans le sous-arbre gauche d’un ancêtre contenant a, supérieur à a s’il se trouve dans le sous-arbre droit. Ensemble, ces limites forment un intervalle ouvert (low, high), et le nœud est exactement à la bonne place lorsque sa valeur se trouve strictement à l’intérieur.
Construis l’intervalle en descendant. Un enfant gauche conserve low et reçoit high = v ; un enfant droit conserve high et reçoit low = v. Dans le deuxième exemple, 15 transmet (10, 15) à son enfant gauche, et le 6 échoue immédiatement. Les valeurs sont comprises entre 0 et 10^5, donc -1 et 100001 servent de limites inexistantes. Chaque nœud est vérifié une seule fois, en temps O(n), avec O(h) nœuds sur la pile.
Algorithme
- Empilez
(0, -1, 100001): la racine, sans limite réelle. - Dépilez
(i, low, high). Sitree[i]n’est pas strictement compris entrelowethigh, renvoyezfalse. - Empilez chaque enfant réel : celui de gauche à
2*i+1avec(low, tree[i]), celui de droite à2*i+2avec(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
- Comparer un nœud uniquement avec ses enfants. Dans
[10, 5, 15, -1, -1, 6, 20], chaque paire parent-enfant semble correcte, pourtant le6dépasse la limite de la racine. - Autoriser les valeurs égales.
[12, 7, 12]n'est pas valide : compare avec<, jamais avec≤. - Utiliser
0comme borne inférieure « sans limite ». Cela rejette l'arbre valide[0]. - Lire un enfant sans vérifier
2*i+1 < tree.length. Dans[12, 7, 12], l'index3dépasse la fin. - En Lua et R, les tableaux commencent à 1. Garde les index des nœuds à base 0 pour
2*i+1et listree[i + 1].
Questions fréquentes3
Quelle est la complexité temporelle de la validation d’un arbre binaire de recherche ?
La vérification dans l’ordre infixe et la vérification des plages visitent chaque nœud une fois : un temps de O(n), avec un espace supplémentaire de O(h) pour la pile de la vérification des plages, sur un arbre de profondeur h. Comparer chaque nœud à l’ensemble de ses sous-arbres coûte O(n × h), ce qui atteint O(n²) sur un arbre en forme de chemin.
Peux-tu valider un BST à l’aide d’un parcours infixe sans stocker toutes les valeurs ?
Oui. La vérification compare uniquement chaque valeur à celle qui la précède ; conservez donc la valeur précédente dans une variable plutôt que dans une liste, et renvoyez false dès qu’une valeur n’est pas supérieure. L’espace supplémentaire passe à O(h) pour la récursion ou la pile.
Un arbre binaire de recherche peut-il contenir des valeurs dupliquées ?
Pas selon la définition stricte utilisée ici : une valeur égale ne convient d’aucun côté. Certains manuels autorisent les valeurs égales d’un côté, par exemple à droite. Selon cette règle, une comparaison stricte devient ≤.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def isValidBST(tree):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
tree = [8, 3, 12, 1, 6, 10, 15]
Résultat attendu
true