Validate Binary Search Tree

Q: Perché controllare ogni nodo rispetto ai suoi figli non basta per convalidare un BST?

La regola riguarda interi sottoalberi. Un nodo in profondità nel sottoalbero destro della radice deve essere maggiore della radice, anche se è il figlio sinistro di un nodo molto più grande. In [10, 5, 15, -1, -1, 6, 20] , il 6 è un valido figlio sinistro di 15 , ma si trova a destra di 10 , quindi l'albero non è un albero di ricerca. Devi considerare i limiti di ogni antenato, non solo del genitore.

Q: Qual è la complessità temporale della convalida di un albero di ricerca binario?

Entrambi i metodi standard, il controllo in ordine simmetrico e il controllo dell'intervallo, visitano ogni nodo una volta, quindi richiedono O(n) di tempo. Il controllo dell'intervallo richiede O(h) di spazio aggiuntivo per lo stack, dove h è la profondità. Anche confrontare ogni nodo con i suoi interi sottoalberi funziona, ma ha un costo di O(n × h) , che raggiunge O(n²) in un albero a forma di percorso.

Q: Riesci a convalidare un BST con una visita in ordine senza memorizzare ogni valore?

Sì. Il controllo in ordine confronta sempre e solo un valore con quello immediatamente precedente, quindi conserva il valore precedente in una variabile invece che in un elenco. Percorri l’albero in ordine con la ricorsione o con uno stack esplicito e restituisci false non appena un valore non è maggiore del precedente. In questo modo, lo spazio aggiuntivo si riduce a O(h) .

Q: Un albero di ricerca binario può contenere valori duplicati?

Non secondo la definizione rigorosa usata qui: ogni valore a sinistra deve essere minore e ogni valore a destra maggiore, quindi due valori uguali non possono mai essere entrambi compatibili. Alcuni libri di testo consentono i duplicati da un lato, per esempio i valori uguali a destra. Secondo quella regola, cambieresti una delle comparazioni strette in ≤ , quindi leggi la definizione prima di scrivere il controllo.

MedioAlbero binario di ricerca Visita di alberi

+10

Ti viene dato un albero binario 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), -1 indica una posizione vuota e l'array può terminare con ulteriori voci -1.

Scrivi una funzione chiamata isValidBST che restituisca true se l'albero è un albero di ricerca binaria e false altrimenti. In un albero di ricerca binaria, il valore di ogni nodo è strettamente maggiore di tutti i valori del suo sottoalbero sinistro e strettamente minore di tutti i valori del suo sottoalbero destro. Due valori uguali non possono mai trovarsi entrambi in un albero valido.

Funzione

isValidBST(tree: integer-array) → boolean

treeinteger-array: l’albero binario in ordine per livelli, con -1 per una posizione vuota
Restituisceboolean: vero se l'albero è un albero binario di ricerca, falso altrimenti

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.
I valori possono ripetersi.

Esempi

Input: tree = [8, 3, 12, 1, 6, 10, 15]
Output: true
Spiegazione: Ogni nodo si trova sul lato corretto di ogni nodo sopra di esso. Leggendo in ordine (sottoalbero sinistro, nodo, sottoalbero destro), i valori risultano 1, 3, 6, 8, 10, 12, 15, strettamente crescenti, come accade in un albero di ricerca.

Input: tree = [10, 5, 15, -1, -1, 6, 20]
Output: false
Spiegazione: Ogni nodo è più grande del figlio sinistro e più piccolo del figlio destro, eppure l’albero non è valido. Il 6 all’indice 5 si trova nel sottoalbero destro della radice 10, quindi deve essere più grande di 10, ma non lo è.

Input: tree = [12, 7, 12]
Output: false
Spiegazione: Il figlio destro della radice contiene 12, lo stesso valore della radice. Il sottoalbero destro deve essere strettamente maggiore, quindi un valore uguale viola la regola.

+16 test nascosti all’invio

Per approfondire

Il genitore del nodo all’indice i si trova in (i-1)/2, arrotondato per difetto. Riesci a percorrere l’albero in ordine con spazio aggiuntivo O(1), spostandoti tra i genitori invece di mantenere uno stack o usare la ricorsione?

Suggerimenti

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

0 di 3 aperti

Soluzione

La regola riguarda interi sottoalberi, non un nodo e i suoi due figli. Un albero può superare il controllo di genitore e figli in ogni nodo ed essere comunque errato, perché un nodo in profondità può violare un limite stabilito da un antenato diversi livelli più in alto. Due idee risolvono il problema in modo semplice: leggere l’albero in ordine e verificare che i valori aumentino strettamente, oppure passare a ogni nodo l’intervallo di valori consentito dai suoi antenati e verificare che il nodo rientri in tale intervallo.

Confronta ogni nodo con i suoi interi sottoalberi

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 [10, 5, 15, -1, -1, 6, 20], la radice 10 ha 5 e 15 agli indici 1 e 2, e il nodo 15 ha 6 e 20 agli indici 5 e 6.

La prima idea che viene in mente alla maggior parte delle persone confronta ogni nodo solo con i suoi due figli. Quell’albero mostra perché non funziona: 5 < 10, 15 > 10, 6 < 15 e 20 > 15 sono tutte condizioni vere, ma il nodo 6 si trova a destra di 10. La definizione parla di ogni valore in un sottoalbero, quindi è proprio questo che bisogna verificare.

Per un nodo che contiene v, tutti i valori a sinistra sono minori di v esattamente quando il valore massimo a sinistra è minore di v. Allo stesso modo, tutti i valori a destra sono maggiori di v quando il valore minimo lì presente è maggiore di v. Due piccoli helper ricorsivi trovano rispettivamente il valore massimo e il valore minimo. Per un lato vuoto, il valore massimo è -1 e il valore minimo è 100001, valori fuori dall’intervallo consentito, quindi un lato vuoto non causa mai un errore.

Questo è corretto, ma ripete il lavoro. Un nodo viene esaminato una volta per ogni antenato che lo sovrasta, quindi il totale è circa n × h visite per un albero di profondità h. Qui una profondità massima di 14 va bene, ma in un albero formato da un unico percorso di n nodi, il costo cresce fino a O(n²).

Algoritmo

Esamina ogni indice i il cui valore non è -1.
Trova il valore più grande nel sottoalbero sinistro che inizia da 2*i+1, oppure -1 se quella posizione è vuota.
Trova il valore più piccolo nel sottoalbero destro che inizia da 2*i+2, oppure 100001 se quella posizione è vuota.
Se il valore più grande è maggiore o uguale a tree[i], oppure il valore più piccolo è minore o uguale a tree[i], restituisci false.
Dopo l'ultimo nodo, restituisci 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 True

I valori in ordine simmetrico devono aumentare strettamente

Intuizione

Una visita in ordine attraversa il sottoalbero sinistro, poi il nodo e infine il sottoalbero destro. In un albero binario di ricerca, quest’ordine è ordinato: tutto ciò che si trova a sinistra è più piccolo, quindi viene prima, e tutto ciò che si trova a destra è più grande, quindi viene dopo. Il primo esempio restituisce 1, 3, 6, 8, 10, 12, 15.

Vale anche il contrario, ed è questo che rende il procedimento un test. Prendi un nodo qualsiasi v. Nella sequenza in ordine, tutto il suo sottoalbero sinistro si trova immediatamente prima di esso e tutto il suo sottoalbero destro immediatamente dopo. Se la sequenza è strettamente crescente, ogni valore precedente a v è minore e ogni valore successivo è maggiore, quindi la regola vale per v e, allo stesso modo, per ogni altro nodo.

Quindi visita l’albero in ordine, raccogli i valori e confronta ciascuno con quello precedente. Il secondo esempio restituisce 5, 10, 6, 15, 20: il passaggio da 10 a 6 rivela il nodo sul lato sbagliato. Il terzo restituisce 7, 12, 12 e il 12 ripetuto non supera il controllo rigoroso. Ogni nodo viene visitato una volta: tempo O(n) e la lista occupa spazio O(n).

Algoritmo

Scrivi walk(i): se la posizione è vuota, fermati; altrimenti visita 2*i+1, aggiungi tree[i], poi visita 2*i+2.
Chiama walk(0) per raccogliere i valori in ordine.
Per ogni posizione k a partire da 1, se values[k-1] ≥ values[k], restituisci false.
Restituisci 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 True

Trasporta l’intervallo consentito lungo l’albero

Intuizione

Osserva la regola dal punto di vista di un nodo. Ogni antenato gli impone un limite. Se il nodo si trova nel sottoalbero sinistro di un antenato che contiene a, il suo valore deve essere minore di a; se si trova nel sottoalbero destro, maggiore di a. Tutti questi limiti insieme formano un intervallo aperto (low, high), e il nodo si trova nella posizione corretta esattamente quando il suo valore rientra strettamente in tale intervallo.

Puoi costruire questo intervallo man mano che scendi. La radice non ha limiti. Passando da un nodo che contiene v al suo figlio sinistro, mantieni low e abbassi high a v; passando al figlio destro, mantieni high e alzi low a v. Il nuovo limite è sempre più restrittivo di quello che sostituisce, perché v stesso ha superato il controllo rispetto al vecchio intervallo.

Nel secondo esempio, 15 riceve l'intervallo (10, no limit) e lo passa al suo figlio sinistro come (10, 15). 6 è minore di 10, quindi il controllo fallisce proprio lì, senza esaminare nessun altro nodo. I valori sono compresi tra 0 e 10^5, quindi -1 e 100001 fungono da «nessun limite».

Conserva i nodi in attesa su uno stack, ciascuno con il proprio intervallo. Ogni nodo viene controllato una volta: tempo O(n); lo stack contiene i nodi in attesa lungo un percorso: spazio O(h). Il primo intervallo non valido interrompe la ricerca.

Algoritmo

Inserisci (0, -1, 100001): l'indice della radice e un intervallo aperto senza limiti reali.
Estrai (i, low, high). Se tree[i] non è strettamente compreso tra low e high, restituisci false.
Se il figlio sinistro 2*i+1 esiste, inseriscilo con l'intervallo (low, tree[i]).
Se il figlio destro 2*i+2 esiste, inseriscilo con l'intervallo (tree[i], high).
Quando lo stack è vuoto, restituisci 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

Trappole e casi limite

La maggior parte delle risposte errate controlla troppo poco oppure controlla la cosa giusta usando il confronto sbagliato.

Confrontare un nodo solo con i suoi figli. In [10, 5, 15, -1, -1, 6, 20] ogni coppia genitore-figlio sembra corretta, ma 6 viola comunque il limite impostato dalla radice due livelli più in alto.
Consentire valori uguali. L'ordine è rigoroso su entrambi i lati, quindi [12, 7, 12] non è valido. Usa low < v < high e values[k-1] < values[k], mai ≤.
Passare solo il valore del genitore. Un figlio sinistro ha bisogno di entrambi i limiti: essere minore del genitore e maggiore dell'eventuale limite inferiore del genitore. Mantieni l'intero intervallo.
Scegliere un valore «nessun limite» che un nodo può contenere. I valori partono da 0, quindi un limite inferiore pari a 0 rifiuterebbe un nodo valido che contiene 0, come in [0]. Parti da un valore inferiore a tutti quelli consentiti.
Leggere oltre la fine dell'array. Controlla 2*i+1 < tree.length prima di leggere un figlio 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 partire da 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti4

Perché controllare ogni nodo rispetto ai suoi figli non basta per convalidare un BST?

La regola riguarda interi sottoalberi. Un nodo in profondità nel sottoalbero destro della radice deve essere maggiore della radice, anche se è il figlio sinistro di un nodo molto più grande. In [10, 5, 15, -1, -1, 6, 20], il 6 è un valido figlio sinistro di 15, ma si trova a destra di 10, quindi l'albero non è un albero di ricerca. Devi considerare i limiti di ogni antenato, non solo del genitore.

Qual è la complessità temporale della convalida di un albero di ricerca binario?

Entrambi i metodi standard, il controllo in ordine simmetrico e il controllo dell'intervallo, visitano ogni nodo una volta, quindi richiedono O(n) di tempo. Il controllo dell'intervallo richiede O(h) di spazio aggiuntivo per lo stack, dove h è la profondità. Anche confrontare ogni nodo con i suoi interi sottoalberi funziona, ma ha un costo di O(n × h), che raggiunge O(n²) in un albero a forma di percorso.

Riesci a convalidare un BST con una visita in ordine senza memorizzare ogni valore?

Sì. Il controllo in ordine confronta sempre e solo un valore con quello immediatamente precedente, quindi conserva il valore precedente in una variabile invece che in un elenco. Percorri l’albero in ordine con la ricorsione o con uno stack esplicito e restituisci false non appena un valore non è maggiore del precedente. In questo modo, lo spazio aggiuntivo si riduce a O(h).

Un albero di ricerca binario può contenere valori duplicati?

Non secondo la definizione rigorosa usata qui: ogni valore a sinistra deve essere minore e ogni valore a destra maggiore, quindi due valori uguali non possono mai essere entrambi compatibili. Alcuni libri di testo consentono i duplicati da un lato, per esempio i valori uguali a destra. Secondo quella regola, cambieresti una delle comparazioni strette in ≤, quindi leggi la definizione prima di scrivere il controllo.

Python

def isValidBST(tree):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

tree = [8, 3, 12, 1, 6, 10, 15]

Atteso

true

Validate Binary Search Tree

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Confronta ogni nodo con i suoi interi sottoalberi

I valori in ordine simmetrico devono aumentare strettamente

Trasporta l’intervallo consentito lungo l’albero

Trappole e casi limite

Domande frequenti4

Problemi simili