Range Sum of BST

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

Una visita che esclude i rami sfruttando l’ordinamento dell’albero di ricerca visita i nodi k nell’intervallo più i nodi lungo al massimo due percorsi dalla radice, con tempo O(h + k) per un albero di profondità h . Nel caso peggiore, quando ogni valore rientra nell’intervallo, è O(n) . Lo spazio aggiuntivo è O(h) per lo stack o la ricorsione.

Q: Perché puoi saltare i sottoalberi in Range Sum of BST?

In un albero di ricerca binario, ogni valore a sinistra di un nodo è minore del suo e ogni valore a destra è maggiore. Se il valore del nodo è al massimo low , nessun valore alla sua sinistra può rientrare nell’intervallo; se è almeno high , nessun valore alla sua destra può farlo. Saltare quei lati non farà mai perdere un valore compreso nell’intervallo.

Q: È possibile risolvere la somma dell'intervallo di un BST con una visita in-order?

Sì. Una visita in ordine di un albero binario di ricerca elenca i valori in ordine crescente, quindi puoi sommare i valori una volta raggiunto low e fermarti non appena uno supera high . Il risultato è lo stesso e l’interruzione anticipata fa risparmiare lavoro sul lato destro dell’albero, mentre la ricerca con potatura fa risparmiare lavoro anche sul lato sinistro.

Q: Dovresti usare la ricorsione o uno stack per la somma degli intervalli di un BST?

Entrambi funzionano. La ricorsione è più breve e, in questo caso, la profondità è al massimo 14, quindi lo stack delle chiamate rimane piccolo. Uno stack esplicito evita completamente il limite di ricorsione, cosa importante per un albero alto con migliaia di livelli, ed è quello che usano le soluzioni in questa pagina.

FacileAlbero binario di ricerca Visita di alberi

+10

Ti viene fornito un albero binario di ricerca memorizzato nell'array tree in ordine per livelli, e due numeri low e high. 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), -1 indica una posizione vuota e l'array può terminare con ulteriori elementi -1. In un albero binario di ricerca, ogni valore nel sottoalbero sinistro di un nodo è minore del valore del nodo, mentre ogni valore nel sottoalbero destro è maggiore.

Scrivi una funzione chiamata rangeSumBST che restituisca la somma di tutti i valori dei nodi v tali che low ≤ v ≤ high, oppure 0 se nessun valore rientra in quell'intervallo.

Funzione

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

treeinteger-array: l'albero binario di ricerca 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 è rappresentabile 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 sono fuori dall’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 essi si trova tra 60 e 70, quindi la somma è 0. Le quattro voci -1 sono i posti vuoti 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.

+14 test nascosti all’invio

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

Sommare ogni valore nell'intervallo è una semplice visita: visita ogni nodo e conserva quelli che rientrano nell'intervallo. L'ordinamento dell'albero di ricerca ti permette di fare di meglio. Il valore di un nodo ti indica su quale lato si trovano i valori più piccoli e quelli più grandi, così puoi saltare interi sottoalberi senza esaminare nemmeno un nodo al loro interno.

Visita ogni nodo

Intuizione

Per prima cosa, vediamo come spostarsi nell’array. Il nodo all’indice i ha il figlio sinistro all’indice 2*i+1 e il figlio destro all’indice 2*i+2. Un figlio esiste solo se il suo indice è all’interno dell’array e il valore corrispondente non è -1. In [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15], la radice 20 ha 8 e 31 agli indici 1 e 2; il nodo 12 all’indice 4 ha 10 e 15 agli indici 9 e 10, e il nodo 31 ha uno spazio vuoto a sinistra all’indice 5.

Passiamo ora all’idea. Ogni valore nell’intervallo si trova in un nodo, quindi una visita che raggiunge ogni nodo e somma i valori per cui low ≤ v ≤ high ottiene la somma corretta. Usa uno stack di indici dei nodi. Parti dalla radice, estrai un indice, aggiungi il suo valore se rientra nell’intervallo e inserisci ogni figlio esistente.

Questo ignora completamente la proprietà dell’albero di ricerca: funziona con qualsiasi albero binario. Visita tutti gli n nodi, con un tempo O(n), e lo stack contiene i figli in attesa lungo un percorso, usando uno spazio O(h) per una profondità h. Quando l’intervallo comprende pochi valori in un albero di migliaia di nodi, gran parte del lavoro è sprecata.

Algoritmo

Inserisci l'indice della 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 seguendo l’ordine dell’albero di ricerca

Intuizione

Mantieni la stessa visita dell'albero con uno stack, ma sfrutta l'ordinamento. Supponiamo che un nodo contenga v. Il suo sottoalbero sinistro contiene solo valori minori di v. Se v ≤ low, tutti i valori sono minori di low, quindi il sottoalbero sinistro non può aggiungere nulla: saltalo. Allo stesso modo, se v ≥ high, il sottoalbero destro contiene solo valori maggiori di high: saltalo. Quindi inserisci il figlio sinistro nello stack solo quando v > low e il figlio destro solo quando v < high.

Nel primo esempio, con l'intervallo [9, 31], 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, mentre il figlio destro 12 viene comunque visitato, perché i valori compresi tra 8 e 20 possono rientrare nell'intervallo.

I nodi visitati sono i k valori nell'intervallo, più al massimo due percorsi dalla radice a una foglia lungo i suoi bordi, quindi il tempo è O(h + k). Quando l'intervallo copre l'intero albero, la complessità resta O(n), ma un intervallo ristretto in un albero grande tocca solo poche decine di nodi. Lo stack richiede O(h) spazio.

Algoritmo

Inserisci l’indice della 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 esiste.
Se v < high, inserisci il figlio destro 2*i+2 quando esiste.
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

La maggior parte delle risposte errate dipende dai limiti dell'intervallo o dell'array.

Usare confronti stretti. Entrambi gli estremi sono inclusi, quindi anche un nodo uguale a low o high conta.
Potare un passaggio troppo presto. Quando v è uguale a low, si può saltare il sottoalbero sinistro, ma quando v è low + 1 non si può: potrebbe contenere proprio low.
Fermarsi a un nodo fuori dall'intervallo. Un nodo minore di low può comunque avere un sottoalbero destro pieno di valori nell'intervallo, quindi salta solo il lato che le regole dell'ordinamento escludono.
Leggere l'indice di un figlio oltre la fine dell'array. Controlla 2*i+1 < tree.length prima di leggere il valore e considera -1 come assenza di un figlio.
Confondere l'offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a base 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti4

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

Una visita che esclude i rami sfruttando l’ordinamento dell’albero di ricerca visita i nodi k nell’intervallo più i nodi lungo al massimo due percorsi dalla radice, con tempo O(h + k) per un albero di profondità h. Nel caso peggiore, quando ogni valore rientra nell’intervallo, è O(n). Lo spazio aggiuntivo è O(h) per lo stack o la ricorsione.

Perché puoi saltare i sottoalberi in Range Sum of BST?

In un albero di ricerca binario, ogni valore a sinistra di un nodo è minore del suo e ogni valore a destra è maggiore. Se il valore del nodo è al massimo low, nessun valore alla sua sinistra può rientrare nell’intervallo; se è almeno high, nessun valore alla sua destra può farlo. Saltare quei lati non farà mai perdere un valore compreso nell’intervallo.

È possibile risolvere la somma dell'intervallo di un BST con una visita in-order?

Sì. Una visita in ordine di un albero binario di ricerca elenca i valori in ordine crescente, quindi puoi sommare i valori una volta raggiunto low e fermarti non appena uno supera high. Il risultato è lo stesso e l’interruzione anticipata fa risparmiare lavoro sul lato destro dell’albero, mentre la ricerca con potatura fa risparmiare lavoro anche sul lato sinistro.

Dovresti usare la ricorsione o uno stack per la somma degli intervalli di un BST?

Entrambi funzionano. La ricorsione è più breve e, in questo caso, la profondità è al massimo 14, quindi lo stack delle chiamate rimane piccolo. Uno stack esplicito evita completamente il limite di ricorsione, cosa importante per un albero alto con migliaia di livelli, ed è quello che usano le soluzioni in questa pagina.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso