Range Sum of BST

Q: Qual è la complessità temporale di Range Sum of BST?

La visita potata attraversa i k nodi nell’intervallo più i nodi lungo al massimo due percorsi dalla radice: tempo O(h + k) per un albero di profondità h e O(n) quando ogni valore rientra nell’intervallo. Lo stack o la ricorsione occupano O(h) spazio.

Q: È possibile risolvere Range Sum of BST con una visita in-order?

Sì. Una visita in ordine elenca i valori in ordine crescente, quindi aggiungi i valori quando raggiungono low e ti fermi al primo che supera high . L’interruzione anticipata fa risparmiare lavoro sul lato destro dell’albero; il pruning lo fa risparmiare su entrambi i lati.

Q: Dovresti usare la ricorsione o uno stack per la somma dell’intervallo di un BST?

Entrambi funzionano. Qui la profondità è al massimo 14, quindi la ricorsione resta poco profonda. Uno stack esplicito evita il limite di ricorsione in un albero alto con migliaia di livelli.

FacileAlbero binario di ricerca Visita di alberi

+10

Un albero binario di ricerca è memorizzato nell'array tree in ordine per livelli: la radice si trova all'indice 0, i figli del nodo all'indice i si trovano agli indici 2*i+1 (sinistro) e 2*i+2 (destro) e -1 indica una posizione vuota. In un albero binario di ricerca, ogni valore nel sottoalbero sinistro di un nodo è minore del valore del nodo e ogni valore nel suo sottoalbero destro è maggiore.

Restituisci la somma di tutti i valori dei nodi v per cui low ≤ v ≤ high, oppure 0 se non ce ne sono.

Funzione

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

treeinteger-array: l'albero di ricerca binario in ordine per livelli, con -1 per una posizione vuota
lowinteger: il valore più piccolo da contare
highinteger: il valore più grande da contare
Restituisceinteger: la somma dei valori dei nodi compresi tra low e high, inclusi

Vincoli

1 ≤ tree.length ≤ 32767
Ogni tree[i] è -1 oppure un valore con 0 ≤ tree[i] ≤ 10⁵.
tree[0] non è mai -1, quindi l’albero ha almeno un nodo.
L'array può terminare con voci -1 aggiuntive dopo l'ultimo nodo.
Entrambi i figli di una posizione vuota sono vuoti a loro volta e la profondità è al massimo 14.
L'albero è un albero binario di ricerca valido, quindi tutti i suoi valori sono distinti.
0 ≤ low ≤ high ≤ 10⁵
La risposta rientra in un intero con segno a 32 bit.

Esempi

Input: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Output: 88
Spiegazione: I valori da 9 a 31 sono 10, 12, 15, 20 e 31, che sommati danno 88. 3, 8 e 40 non rientrano nell’intervallo.

Input: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Output: 0
Spiegazione: L’albero contiene 25, 50 e 75, e nessuno di questi si trova tra 60 e 70, quindi la somma è 0. Le quattro voci -1 sono le posizioni vuote dei figli di 25 e 75.

Input: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Output: 4
Spiegazione: Con low e high entrambi pari a 4, conta solo un nodo di valore 4. Il 4 all'indice 4 è il figlio destro di 2, quindi la risposta è 4.

Per approfondire

Se dovessi rispondere a migliaia di query diverse (low, high) sullo stesso albero, come potresti rispondere a ciascuna in tempo O(log n)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Visitare ogni nodo e sommare i valori nell'intervallo è corretto. L'ordinamento dell'albero di ricerca ti permette di fare meno: il valore di un nodo ti indica da quale parte si trovano i valori più piccoli e quelli più grandi, quindi un sottoalbero che non può contenere valori nell'intervallo non viene mai esplorato.

Visita ogni nodo

Intuizione

Un figlio esiste solo se il suo indice è all'interno dell'array e il valore in quella posizione non è -1. Nel primo esempio, 12 all'indice 4 ha 10 e 15 agli indici 9 e 10, e 31 all'indice 2 ha una posizione sinistra vuota all'indice 5.

Ogni valore nell'intervallo si trova in un nodo, quindi una visita con stack che raggiunge ogni nodo e somma i valori con low ≤ v ≤ high restituisce la somma corretta. Ignora l'ordine dell'albero di ricerca, quindi visita tutti gli n nodi anche quando l'intervallo contiene solo pochi valori.

Algoritmo

Inserisci l'indice radice 0 in uno stack e imposta total = 0.
Estrai un indice i. Se low ≤ tree[i] ≤ high, aggiungi tree[i] a total.
Inserisci 2*i+1 e 2*i+2 quando si trovano all'interno dell'array e non sono -1.
Quando lo stack è vuoto, restituisci 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

Potare secondo l'ordine dell'albero di ricerca

Intuizione

Il sottoalbero sinistro di un nodo che contiene v ha solo valori minori di v. Se v ≤ low, nessuno di essi rientra nell’intervallo, quindi salta quel sottoalbero. Se v ≥ high, il sottoalbero destro contiene solo valori maggiori di high, quindi saltalo. Nel primo esempio 31 è uguale a high, quindi il suo figlio destro 40 non viene mai inserito nello stack. 8 è minore di low, quindi il suo figlio sinistro 3 viene saltato, ma il suo figlio destro 12 viene visitato, perché i valori compresi tra 8 e 20 possono rientrare nell’intervallo.

Visiti i k valori nell’intervallo, oltre ai nodi che si trovano al massimo su due percorsi dalla radice: tempo O(h + k) per una profondità h. Quando l’intervallo copre l’intero albero, la complessità è comunque O(n).

Algoritmo

Inserisci l'indice radice 0 in uno stack e imposta total = 0.
Estrai un indice i e leggi v = tree[i]. Se low ≤ v ≤ high, aggiungi v a total.
Se v > low, inserisci il figlio sinistro 2*i+1 quando è reale.
Se v < high, inserisci il figlio destro 2*i+2 quando è reale.
Quando lo stack è vuoto, restituisci 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

Trappole e casi limite

Usare confronti stretti. Entrambi gli estremi sono inclusi, quindi il terzo esempio, con low = high = 4, deve includere il 4.
Potare un livello troppo presto. Con v = low si può eliminare il sottoalbero sinistro, ma con v = low + 1 potrebbe contenere proprio low.
Eliminare entrambi i lati di un nodo fuori dall'intervallo. L'8 nel primo esempio è minore di low, ma il suo sottoalbero destro contiene 10, 12 e 15.
Leggere un figlio oltre la fine dell'array. Controlla 2*i+1 < tree.length prima di leggere e considera -1 come assenza di un figlio.
In Lua e R, gli array iniziano da 1: mantieni gli indici dei nodi a partire da 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti3

Qual è la complessità temporale di Range Sum of BST?

La visita potata attraversa i k nodi nell’intervallo più i nodi lungo al massimo due percorsi dalla radice: tempo O(h + k) per un albero di profondità h e O(n) quando ogni valore rientra nell’intervallo. Lo stack o la ricorsione occupano O(h) spazio.

È possibile risolvere Range Sum of BST con una visita in-order?

Sì. Una visita in ordine elenca i valori in ordine crescente, quindi aggiungi i valori quando raggiungono low e ti fermi al primo che supera high. L’interruzione anticipata fa risparmiare lavoro sul lato destro dell’albero; il pruning lo fa risparmiare su entrambi i lati.

Dovresti usare la ricorsione o uno stack per la somma dell’intervallo di un BST?

Entrambi funzionano. Qui la profondità è al massimo 14, quindi la ricorsione resta poco profonda. Uno stack esplicito evita il limite di ricorsione in un albero alto con migliaia di livelli.

def rangeSumBST(tree, low, high):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso