Elimina sequenza ordinata di numeri da BST

Ho avuto questa domanda durante un esame e non sono riuscito a trovare una risposta rapida.Elimina sequenza ordinata di numeri da BST

C'è un array A contenente alcuni numeri ordinati A = [1,3,6,9,11] e un BST con numeri come chiave. Devo fornire un algoritmo ricorsivo efficiente per cancellare i numeri in A dal BST.

Il problema che ho non è nell'eliminare i nodi, ma in come usare il fatto che l'array è ordinato nell'eliminare i nodi.

Qualcuno può aiutarmi con alcuni suggerimenti?

fonte

2011-09-01 JustB

http://en.wikipedia.org/wiki/Binary_search_tree#Deletion – quasiverse

c'è una soluzione O (n + k) per questo. Per gli alberi non bilanciati è il meglio che puoi ottenere perché devi leggere tutti gli elementi dell'array [O (k)] ed eliminare un elemento in un BST non bilanciato è O (n) [elimina l'ultimo elemento in un catena] ci sei stato dentro? o stai cercando qualcosa di più ottimizzato per BST bilanciato? – amit

Grazie mille: non ho ipotesi sull'albero quindi devo considerare tutti i casi. – JustB

Ecco un possibile approccio.

È possibile attraversare contemporaneamente sia il BST (utilizzando il standard recursive algorithm) sia il A (da sinistra a destra). Ciascuno degli attraversamenti produrrà elementi in ordine crescente. Stai cercando gli elementi corrispondenti per eliminarli dall'albero.

Un algoritmo ingenuo avrà una complessità temporale pari a O(size(BST)).

In alcuni casi è possibile evitare di guardare completamente il sottoalbero sinistro: il valore del nodo "corrente" nell'albero fornisce un limite superiore ai valori nel sottostruttura sinistro, quindi se questo è inferiore al valore di l'elemento "corrente" di A, salta la sottostruttura di sinistra.

È anche possibile interrompere l'algoritmo non appena è stato esaurito A.

fonte

2011-09-01 11:16:20 NPE

Lascia che un BST sia rappresentato dal suo nodo radice.

La funzione delete-array-from-bst con argomenti array e bst è:

se la array o bst è vuota: tornare
dividere la matrice in tre sottoarray, i valori più piccoli, uguali, e più grande della Valore del nodo radice bst
recurse sul subarray con i valori più piccoli con il sub-BST sinistro, quindi sul subarray con i valori più grandi sul sotto-BST destro, infine eliminare il valore uguale, se appli cavo

La divisione dell'array è una ricerca binaria, pertanto non è necessario confrontare ciascun valore di matrice con il nodo radice. I sottoarray possono condividere la struttura con l'array originale. L'eliminazione dell'ultimo valore equivale a garantire che non si verifichi il caso peggiore di eliminazione per ciascun valore nell'array.

fonte

2011-09-01 11:46:19 Svante

Elimina sequenza ordinata di numeri da BST

risposta

Problemi correlati