Range Sum of BST

Q: Quelle est la complexité temporelle de Range Sum of BST ?

Un parcours qui élagage en fonction de l’ordre de l’arbre de recherche visite les k nœuds de l’intervalle ainsi que les nœuds situés sur au plus deux chemins depuis la racine, en O(h + k) pour un arbre de profondeur h . Dans le pire des cas, lorsque toutes les valeurs sont dans l’intervalle, cela donne O(n) . L’espace supplémentaire est de O(h) pour la pile ou la récursion.

Q: Pourquoi pouvez-vous ignorer des sous-arbres dans Range Sum of BST ?

Dans un arbre binaire de recherche, chaque valeur à gauche d’un nœud est inférieure à celle-ci, et chaque valeur à droite est supérieure. Si la valeur du nœud est inférieure ou égale à low , aucune valeur à sa gauche ne peut appartenir à l’intervalle, et si elle est supérieure ou égale à high , aucune valeur à sa droite ne le peut. Ignorer ces côtés ne fait manquer aucune valeur de l’intervalle.

Q: Peut-on résoudre la somme d'une plage dans un BST avec un parcours infixe ?

Oui. Un parcours infixe d’un arbre binaire de recherche énumère les valeurs dans l’ordre croissant : tu peux donc additionner les valeurs dès qu’elles atteignent low et t’arrêter dès que l’une dépasse high . Le résultat est le même, et l’arrêt anticipé évite du travail dans la partie droite de l’arbre, tandis que la recherche élaguée en évite aussi dans la partie gauche.

Q: Faut-il utiliser la récursivité ou une pile pour calculer la somme d’une plage dans un BST ?

Les deux fonctionnent. La récursion est plus courte, et ici la profondeur est d’au plus 14, donc la pile d’appels reste réduite. Une pile explicite évite entièrement la limite de récursion, ce qui est important pour un arbre très haut comptant des milliers de niveaux, et c’est ce qu’utilisent les solutions de cette page.

FacileArbre binaire de recherche Parcours d’arbre

+10

On vous donne un arbre binaire de recherche stocké dans le tableau tree en parcours par niveaux, ainsi que deux nombres low et high. 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. Dans un arbre binaire de recherche, chaque valeur du sous-arbre gauche d’un nœud est inférieure à la valeur de ce nœud, et chaque valeur de son sous-arbre droit est supérieure.

Écrivez une fonction nommée rangeSumBST qui renvoie la somme de toutes les valeurs de nœud v telles que low ≤ v ≤ high, ou 0 si aucune valeur ne se trouve dans cet intervalle.

Fonction

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: l’arbre binaire de recherche par ordre de niveaux, avec -1 pour une place vide
lowinteger: la plus petite valeur à compter
highinteger: la plus grande valeur à compter
Renvoieinteger: la somme des valeurs des nœuds comprises entre low et high, bornes incluses

Contraintes

1 ≤ tree.length ≤ 32767
Chaque tree[i] est -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 au plus de 14.
L’arbre est un arbre binaire de recherche valide, donc toutes ses valeurs sont distinctes.
0 ≤ low ≤ high ≤ 10⁵
La réponse tient dans un entier signé de 32 bits.

Exemples

Entrée: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Sortie: 88
Explication: Les valeurs de 9 à 31 sont 10, 12, 15, 20 et 31, dont la somme est 88. Les valeurs 3, 8 et 40 sont en dehors de l’intervalle.

Entrée: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Sortie: 0
Explication: L’arbre contient 25, 50 et 75, et aucun d’eux ne se trouve entre 60 et 70, donc la somme est 0. Les quatre entrées -1 correspondent aux emplacements des enfants vides de 25 et 75.

Entrée: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Sortie: 4
Explication: Avec low et high tous deux égaux à 4, seul un nœud de valeur 4 est pris en compte. Le 4 à l’index 4 est l’enfant droit de 2, donc la réponse est 4.

+14 tests cachés à la soumission

Pour aller plus loin

Si tu devais répondre à des milliers de requêtes (low, high) différentes sur le même arbre, comment pourrais-tu répondre à chacune en O(log n) ?

Indices

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

0 sur 3 ouverts

Solution

Faire la somme de toutes les valeurs de l’intervalle revient à effectuer un parcours simple : visiter chaque nœud et conserver ceux qui conviennent. L’ordre de l’arbre de recherche permet de faire mieux. La valeur d’un nœud indique de quel côté se trouvent les valeurs plus petites et plus grandes, ce qui permet d’ignorer des sous-arbres entiers sans examiner un seul nœud à l’intérieur.

Visitez chaque nœud

Intuition

D’abord, voyons comment se déplacer dans le tableau. Le nœud à l’index i a son enfant gauche à l’index 2*i+1 et son enfant droit à l’index 2*i+2. Un enfant est réel uniquement si son index se trouve dans le tableau et si la valeur correspondante n’est pas -1. Dans [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15], la racine 20 a 8 et 31 aux index 1 et 2, le 12 à l’index 4 a 10 et 15 aux index 9 et 10, et le 31 a un emplacement gauche vide à l’index 5.

Passons maintenant à l’idée. Chaque valeur de l’intervalle se trouve dans un nœud ; un parcours qui atteint chaque nœud et additionne les valeurs vérifiant low ≤ v ≤ high donne donc la somme voulue. Utilisez une pile d’index de nœuds. Commencez par la racine, dépilez un index, ajoutez sa valeur si elle se trouve dans l’intervalle, puis empilez chaque enfant réel.

Cette approche ignore complètement la propriété d’arbre de recherche ; elle fonctionne sur n’importe quel arbre binaire. Elle parcourt les n nœuds, en temps O(n), et la pile contient les enfants en attente le long d’un chemin, soit un espace de O(h) pour une profondeur h. Lorsque l’intervalle ne couvre que quelques valeurs dans un arbre de plusieurs milliers de nœuds, la majeure partie de ce travail est inutile.

Algorithme

Empilez l’index racine 0 et définissez total = 0.
Dépilez un index i. Si low ≤ tree[i] ≤ high, ajoutez tree[i] à total.
Empilez 2*i+1 et 2*i+2 s’ils se trouvent dans le tableau et ne valent pas -1.
Lorsque la pile est vide, renvoyez total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Élaguer en suivant l’ordre de l’arbre de recherche

Intuition

Conservez le même parcours avec une pile, mais utilisez l’ordre. Supposons qu’un nœud contienne v. Son sous-arbre gauche ne contient que des valeurs inférieures à v. Si v ≤ low, toutes ces valeurs sont inférieures à low, donc le sous-arbre gauche ne peut rien ajouter : ignorez-le. De même, si v ≥ high, le sous-arbre droit ne contient que des valeurs supérieures à high : ignorez-le. Vous n’empilez donc l’enfant gauche que lorsque v > low, et l’enfant droit que lorsque v < high.

Dans le premier exemple, avec l’intervalle [9, 31], 31 est égal à high, donc son enfant droit 40 n’est jamais empilé. 8 est inférieur à low, donc son enfant gauche 3 est ignoré, tandis que son enfant droit 12 est tout de même visité, car les valeurs comprises entre 8 et 20 peuvent appartenir à l’intervalle.

Les nœuds que vous visitez sont les k valeurs de l’intervalle, plus au maximum deux chemins de la racine à une feuille le long de ses bords, donc le temps d’exécution est O(h + k). Lorsque l’intervalle couvre tout l’arbre, cela reste O(n), mais un intervalle étroit dans un grand arbre ne touche qu’une quelques dizaines de nœuds. La pile nécessite un espace de O(h).

Algorithme

Empilez l’indice racine 0 sur une pile et définissez total = 0.
Dépilez un indice i et lisez v = tree[i]. Si low ≤ v ≤ high, ajoutez v à total.
Si v > low, empilez l’enfant gauche 2*i+1 s’il existe.
Si v < high, empilez l’enfant droit 2*i+2 s’il existe.
Lorsque la pile est vide, renvoyez total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Pièges et cas limites

La plupart des mauvaises réponses viennent des limites de l’intervalle ou du tableau.

Utiliser des comparaisons strictes. Les deux extrémités sont incluses, donc un nœud égal à low ou à high compte.
Élaguer une étape trop tôt. Lorsque v est égal à low, on peut ignorer le sous-arbre gauche, mais lorsque v vaut low + 1, ce n’est pas possible : il peut contenir low lui-même.
S’arrêter à un nœud situé hors de l’intervalle. Un nœud inférieur à low peut tout de même avoir un sous-arbre droit rempli de valeurs dans l’intervalle ; ignorez donc seulement le côté exclu par les règles d’ordre.
Lire l’indice d’un enfant au-delà de la fin du tableau. Vérifiez 2*i+1 < tree.length avant de lire la valeur, 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 à base zéro pour le calcul 2*i+1 et lisez tree[i + 1].

Questions fréquentes4

Quelle est la complexité temporelle de Range Sum of BST ?

Un parcours qui élagage en fonction de l’ordre de l’arbre de recherche visite les k nœuds de l’intervalle ainsi que les nœuds situés sur au plus deux chemins depuis la racine, en O(h + k) pour un arbre de profondeur h. Dans le pire des cas, lorsque toutes les valeurs sont dans l’intervalle, cela donne O(n). L’espace supplémentaire est de O(h) pour la pile ou la récursion.

Pourquoi pouvez-vous ignorer des sous-arbres dans Range Sum of BST ?

Dans un arbre binaire de recherche, chaque valeur à gauche d’un nœud est inférieure à celle-ci, et chaque valeur à droite est supérieure. Si la valeur du nœud est inférieure ou égale à low, aucune valeur à sa gauche ne peut appartenir à l’intervalle, et si elle est supérieure ou égale à high, aucune valeur à sa droite ne le peut. Ignorer ces côtés ne fait manquer aucune valeur de l’intervalle.

Peut-on résoudre la somme d'une plage dans un BST avec un parcours infixe ?

Oui. Un parcours infixe d’un arbre binaire de recherche énumère les valeurs dans l’ordre croissant : tu peux donc additionner les valeurs dès qu’elles atteignent low et t’arrêter dès que l’une dépasse high. Le résultat est le même, et l’arrêt anticipé évite du travail dans la partie droite de l’arbre, tandis que la recherche élaguée en évite aussi dans la partie gauche.

Faut-il utiliser la récursivité ou une pile pour calculer la somme d’une plage dans un BST ?

Les deux fonctionnent. La récursion est plus courte, et ici la profondeur est d’au plus 14, donc la pile d’appels reste réduite. Une pile explicite évite entièrement la limite de récursion, ce qui est important pour un arbre très haut comptant des milliers de niveaux, et c’est ce qu’utilisent les solutions de cette page.

Python

def rangeSumBST(tree, low, high):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Attendu