Unione di due alberi di ricerca binaria

0

A che ora in termini di Big O occorrerà unire due BST in One? Ciascuno che non ha né nodi né altezza O (log n) senza elementi comuni.

Il risultato dovrebbe essere anche un BST

    
posta user123 04.11.2015 - 09:57
fonte

1 risposta

1

Il post StackOverflow che @manlio ha indicato è un duplicato esatto. Fondamentalmente, sì, l'algoritmo può essere migliorato a O (n + m); l'approccio è quello di appiattire gli alberi in liste ordinate, unirle e ricreare un BST. Questa pagina ha anche qualche codice di esempio che potrebbe essere di interesse pure.

    
risposta data 23.05.2017 - 14:40
fonte

Leggi altre domande sui tag