Ho una conoscenza di base di come 2-3-4 trees mantiene l'operazione di proprietà del bilanciamento dell'altezza dopo l'operazione per assicurarsi che anche le operazioni del caso peggiore siano O (n logn).Perché non usiamo alberi 2-3 o 2-3-4-5?
Ma non lo capisco abbastanza bene da sapere perché solo 2-3-4?
Perché non 2-3 o 2-3-4-5 ecc.?
Per essere onesti, non ero a conoscenza di 2-3-4 alberi. Nella mia classe Data Structures, ci hanno insegnato 2-3 alberi e, a essere onesti, molti di noi hanno implementato alberi AVL per la parte umida dell'esercizio.
Ma a quanto pare, c'è una generalizzazione di questo tipo di albero: (a,b) tree.
Interessante! Questo significa che non possiamo avere 3-4 alberi, e non sono sicuro del perché? – Lazer
Non ne sono sicuro neanche io. Questo sembra essere un albero piuttosto teorico, e non uno di solito esplorato ... Non ci sono molti alberi (a, b) in rete. – cha0site
Un albero di vettori, bello. :-) –
L'implementazione di 2-3-4 alberi richiede in genere più classi (2NODE, 3NODE, 4NODE) oppure solo NODE con una serie di elementi. Nel caso di più classi si perde molto tempo a costruire e distruggere istanze di nodi e la loro riparazione è ingombrante. Se si utilizza una singola classe con matrici per contenere oggetti e bambini, si sta continuamente ridimensionando gli array che è altrettanto dispendioso o si finisce per sprecare più della metà della memoria su elementi di array non utilizzati. Non è molto efficiente rispetto agli alberi Red-Black.
Gli alberi rosso-nero hanno un solo tipo di struttura del nodo. Poiché gli alberi Red-Black hanno una dualità con 2-3-4 alberi, gli alberi RB possono utilizzare esattamente gli stessi algoritmi di 2-3-4 alberi (non c'è bisogno di stupidamente confuse/complesse implementazioni descritte in Cormen, Leiserson e Rivest che hanno portato ad alberi AA che non sono meno complessi dell'algoritmo 2-3-4.)
Quindi, alberi Red-Black per la loro facilità di implementazione oltre alla loro efficienza memoria/CPU. (Anche gli alberi AVL sono belli. Producono alberi più ben bilanciati e sono stupidi semplicemente per codificare ma tendono ad essere meno efficienti a causa del troppo lavoro per mantenere solo un albero leggermente più compatto.)
Oh, e 2- 3-4-5-6 ... ecc. Non vengono eseguiti perché non si ottiene nulla. 2-3-4 ha un guadagno netto su 2-3 alberi perché possono essere eseguiti senza ricorsività facilmente (la ricorsione tende ad essere meno efficiente, specialmente quando non può essere codificata in coda in modo ricorsivo). Tuttavia, B-Trees e Bplus-Trees sono praticamente 2-3-4-5-6-7-8-9-ecc alberi in cui viene scelta la dimensione massima dei nodi, n, in modo che n record possano essere memorizzati in un singolo settore del disco. (cioè ogni settore del disco è un nodo nell'albero e la dimensione del settore è equivalente al numero di elementi memorizzati nel nodo.) Questo perché il tempo di cercare in modo lineare attraverso 512 record in memoria è ancora MOLTO più veloce che attraversare un livello nell'albero che richiede un altro disco di ricerca/recupero. e O (512) è ancora O (1) e quindi mantiene O (lg n) per l'albero.
Se hai mai implementato un albero 2-3-4 o rosso-nero, sapresti che non è molto banale fare bene e quindi testare. C'è anche una versione semplificata dell'albero rosso-nero, [AA-tree] (http://en.wikipedia.org/wiki/AA_tree), che è meno simmetrica dell'albero rosso-nero, ma sembra essere un buona alternativa ad essa che ha una minore complessità di implementazione. Quando hai bisogno di più sottonodi o alberi piatti, vai per b-tree e sostieni esplicitamente molti sottonodi in modo uniforme. –
Inoltre ci sono sempre le preoccupazioni sulla localizzazione dei dati e overhead per nodo (a causa dei costi degli allocatori). Questi tipi di preoccupazioni tendono a incoraggiare soluzioni basate su array (ad es. Tabelle hash) nella pratica. –