Range Sum of BST

Q: Quelle est la complexité temporelle de la somme d’une plage dans un BST ?

Le parcours élagué visite les k nœuds de l’intervalle ainsi que les nœuds situés sur au plus deux chemins depuis la racine : un temps de O(h + k) pour un arbre de profondeur h , et de O(n) lorsque toutes les valeurs sont dans l’intervalle. La pile ou la récursion nécessite un espace de O(h) .

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

Oui. Un parcours infixe énumère les valeurs par ordre croissant : tu ajoutes donc les valeurs dès qu’elles atteignent low et tu t’arrêtes à la première qui dépasse high . Cet arrêt anticipé évite du travail du côté droit de l’arbre ; l’élagage en évite des deux côtés.

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

Les deux fonctionnent. Ici, la profondeur est d’au plus 14, donc la récursion reste peu profonde. Une pile explicite évite d’atteindre la limite de récursion dans un arbre très haut comptant des milliers de niveaux.

FacileArbre binaire de recherche Parcours d’arbre

+10

Un arbre binaire de recherche est 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), et -1 indique une case vide. Dans un arbre binaire de recherche, chaque valeur du sous-arbre gauche d’un nœud est inférieure à la valeur du nœud, et chaque valeur de son sous-arbre droit lui est supérieure.

Renvoyez la somme de toutes les valeurs de nœud v telles que low ≤ v ≤ high, ou 0 s’il n’y en a aucune.

Fonction

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

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

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 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 eux aussi vides, et la profondeur est au plus 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 se situent 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 vides des enfants 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 comptabilisé. Le 4 à l’index 4 est l’enfant droit de 2, donc la réponse est 4.

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

Parcourir chaque nœud et additionner les valeurs dans l’intervalle est correct. L’ordre de l’arbre de recherche permet d’en faire moins : la valeur d’un nœud vous indique de quel côté se trouvent les valeurs plus petites et les valeurs plus grandes, donc un sous-arbre qui ne peut pas atteindre l’intervalle n’est jamais exploré.

Visitez chaque nœud

Intuition

Un enfant n’est réel que si son indice se trouve dans le tableau et que la valeur à cet emplacement n’est pas -1. Dans le premier exemple, le 12 à l’indice 4 a 10 et 15 aux indices 9 et 10, et le 31 à l’indice 2 a un emplacement gauche vide à l’indice 5.

Chaque valeur de l’intervalle se trouve dans un nœud : un parcours avec une pile qui atteint chaque nœud et additionne les valeurs telles que low ≤ v ≤ high donne donc la somme correcte. Il ignore l’ordre de l’arbre de recherche et parcourt ainsi les n nœuds, même lorsque l’intervalle ne contient que quelques valeurs.

Algorithme

Empile l’indice racine 0 et définis total = 0.
Dépile un indice i. Si low ≤ tree[i] ≤ high, ajoute tree[i] à total.
Empile 2*i+1 et 2*i+2 lorsqu’ils sont dans le tableau et différents de -1.
Lorsque la pile est vide, renvoie 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 selon l’ordre de l’arbre de recherche

Intuition

Le sous-arbre gauche d’un nœud contenant v ne contient que des valeurs inférieures à v. Si v ≤ low, aucune d’elles n’est dans l’intervalle, donc ignore ce sous-arbre. Si v ≥ high, le sous-arbre droit ne contient que des valeurs supérieures à high, donc ignore-le. Dans le premier exemple, 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é, mais son enfant droit 12 est visité, car les valeurs comprises entre 8 et 20 peuvent appartenir à l’intervalle.

Tu visites les k valeurs de l’intervalle ainsi que les nœuds situés sur au plus deux chemins depuis la racine : un temps en O(h + k) pour une profondeur h. Lorsque l’intervalle couvre tout l’arbre, cela reste O(n).

Algorithme

Empile l’index racine 0 et définis total = 0.
Dépile un index i et lis v = tree[i]. Si low ≤ v ≤ high, ajoute v à total.
Si v > low, empile l’enfant gauche 2*i+1 s’il existe.
Si v < high, empile l’enfant droit 2*i+2 s’il existe.
Lorsque la pile est vide, renvoie 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

Utiliser des comparaisons strictes. Les deux bornes sont incluses, donc le troisième exemple, avec low = high = 4, doit compter le 4.
Élaguer une étape trop tôt. À v = low, le sous-arbre gauche peut être éliminé, mais à v = low + 1, il peut contenir low lui-même.
Éliminer les deux côtés d’un nœud situé hors de l’intervalle. Le 8 du premier exemple est inférieur à low, mais son sous-arbre droit contient 10, 12 et 15.
Lire un enfant au-delà de la fin du tableau. Vérifiez 2*i+1 < tree.length avant de lire, et considérez -1 comme l’absence d’enfant.
En Lua et en R, les tableaux commencent à 1 : gardez les index des nœuds à base 0 pour le calcul 2*i+1 et lisez tree[i + 1].

Questions fréquentes3

Quelle est la complexité temporelle de la somme d’une plage dans un BST ?

Le parcours élagué visite les k nœuds de l’intervalle ainsi que les nœuds situés sur au plus deux chemins depuis la racine : un temps de O(h + k) pour un arbre de profondeur h, et de O(n) lorsque toutes les valeurs sont dans l’intervalle. La pile ou la récursion nécessite un espace de O(h).

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

Oui. Un parcours infixe énumère les valeurs par ordre croissant : tu ajoutes donc les valeurs dès qu’elles atteignent low et tu t’arrêtes à la première qui dépasse high. Cet arrêt anticipé évite du travail du côté droit de l’arbre ; l’élagage en évite des deux côtés.

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

Les deux fonctionnent. Ici, la profondeur est d’au plus 14, donc la récursion reste peu profonde. Une pile explicite évite d’atteindre la limite de récursion dans un arbre très haut comptant des milliers de niveaux.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu