Questo non è identico a, ma molto simile a un albero B. È una generalizzazione su un albero di ricerca binario. Un albero di ricerca binario memorizza un valore su ciascun nodo e ha due figli, con il sottoalbero sinistro garantito inferiore a quel nodo e il sottoalbero destro garantito maggiore. Con un albero B, si memorizzano i valori k in ordine ordinato su ciascun nodo e si consente ai bambini k + 1 in base a quale tra due bambini si trova. Questa è fondamentalmente la stessa cosa, tranne che si ha uguaglianza invece di disuguaglianza (dal momento che ci sono solo 26 possibili scelte ad ogni passo). Inoltre, nota come nel tuo caso non stai effettivamente memorizzando i dati su ciascun nodo, ogni nodo usa solo le stesse lettere a-z per determinare quale bambino seguire. Quindi probabilmente conserveresti i bambini alle foglie. Non sono sicuro di come funzionerebbe l'equilibrio; dovresti creare nuovi nodi ogni volta che inserisci una parola che ha lo stesso prefisso di altre parole in termini di nodi che hai già.
Nel tuo caso, devi fornire maggiori dettagli in modo che possiamo rispondere b). Se il tuo elenco di parole è fisso e non cambia, la tua migliore scommessa potrebbe essere semplicemente una semplice matrice. Basta ordinarlo una volta. Quindi per trovare tutte le parole che iniziano con "pippo", basta fare una ricerca binaria per trovare "pippo" e "fopp", o le corrispondenze possibili possibili (arrotondate nelle direzioni appropriate). Quindi restituisci tutte le parole tra di loro. Questo ti darà logN + numResults in tempo complessità. È anche probabile che abbia costanti molto buone in quanto non è necessario seguire molti indicatori in giro. Inoltre ha praticamente zero sovraccarico di spazio. Ovviamente, se si aggiungono regolarmente parole al dizionario, questa non è una buona soluzione dato che l'aggiunta di una parola costa O (N), mentre le soluzioni ad albero probabilmente costano O (logN) per aggiungere una parola.
